Knuth洗牌算法实现Java随机单词生成及数组转换问题排查

需要使用algs4库，基于Knuth洗牌算法从用户输入中选取随机单词。当前程序通过while循环将用户输入收集至ArrayList<String>，但转换为String[]时始终得到空数组——测试输入「hi ho」后输出空数组[]，但ArrayList可正常显示[hi, ho]。同时希望了解两种实现路径：

• 直接将输入转为String[]
• 用Knuth算法对ArrayList进行洗牌

当前代码 #

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class RandomWord {

    public static void main(String[] args) throws IOException {
        StdOut.println("enter your words"); // StdIn.hasNextChar() = !StdIn.isEmpty()
        ArrayList<String> mylist = new ArrayList<String>();
        String store = new String();
        int count = 1;
        String[] arr = new String[mylist.size()];
        int k = 0;
        store = StdIn.readString();
        mylist.add(store);
        if (StdIn.hasNextChar() == false || mylist.contains(null)) {
            StdOut.println("you enter nothing");
        }
        else {
            while (count == mylist.size()) {
                while (StdIn.hasNextChar() == true) {
                    store = StdIn.readString();
                    mylist.add(store);
                    count++;
                    mylist.toArray(arr);
                    System.out.println(Arrays.toString(arr));
                }
            }
        }
    }
}

测试结果 #

enter your words

hi ho // 终端输入

[] // 输出结果

问题分析与解决方案 #

1. 数组为空的核心原因 #

你在初始化String[] arr时，mylist刚创建，size()为0，因此arr是长度为0的空数组。后续调用mylist.toArray(arr)时，由于数组长度不足，方法会返回一个新的、长度匹配的数组，但你没有接收这个返回值，原arr始终是空数组。

2. 修复数组转换问题 #

有两种可靠方式：

• 等ArrayList收集完所有输入后，再创建匹配长度的数组：

  // 所有输入收集完成后执行
  String[] arr = mylist.toArray(new String[mylist.size()]);
  

• 直接接收toArray()的返回值：

  arr = mylist.toArray(new String[0]);
  

3. 直接将输入转为String[]的最简方式 #

利用algs4库提供的StdIn.readAllStrings()方法，一行代码即可获取所有输入的单词数组（自动按空格分割）：

String[] words = StdIn.readAllStrings();

这种方式比手动写循环更简洁、不易出错。

4. 对ArrayList实现Knuth洗牌算法 #

Knuth洗牌的核心逻辑是：遍历集合，对每个位置i，随机选取0 ≤ j ≤ i的位置交换元素。针对ArrayList的实现代码如下：

import edu.princeton.cs.algs4.StdRandom;

public static void knuthShuffle(ArrayList<String> list) {
    int n = list.size();
    for (int i = 0; i < n; i++) {
        // 生成0到i的随机索引
        int j = StdRandom.uniform(i + 1);
        // 交换i和j位置的元素
        String temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }
}

调用时直接传入你的mylist即可，洗牌后可直接选取任意位置的元素作为随机结果（比如取第一个元素）。

优化后的完整代码 #

import java.util.ArrayList;
import java.util.Arrays;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

public class RandomWord {

    // Knuth洗牌算法实现
    public static void knuthShuffle(ArrayList<String> list) {
        int n = list.size();
        for (int i = 0; i < n; i++) {
            int j = StdRandom.uniform(i + 1);
            String temp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);
        }
    }

    public static void main(String[] args) {
        StdOut.println("请输入单词：");
        
        // 方式1：用ArrayList收集输入
        ArrayList<String> mylist = new ArrayList<>();
        while (!StdIn.isEmpty()) {
            mylist.add(StdIn.readString());
        }

        if (mylist.isEmpty()) {
            StdOut.println("你没有输入任何内容");
            return;
        }

        // 转换为String[]并输出
        String[] arr = mylist.toArray(new String[mylist.size()]);
        StdOut.println("转换后的数组：" + Arrays.toString(arr));

        // 对ArrayList洗牌并随机选取单词
        knuthShuffle(mylist);
        StdOut.println("洗牌后的集合：" + mylist);
        StdOut.println("随机选取的单词：" + mylist.get(0));

        // ------------------------------
        // 方式2：直接读取为String[]（注释掉方式1即可启用）
        // StdOut.println("请输入单词：");
        // String[] words = StdIn.readAllStrings();
        // if (words.length == 0) {
        //     StdOut.println("你没有输入任何内容");
        //     return;
        // }
        // // 对数组执行Knuth洗牌
        // for (int i = 0; i < words.length; i++) {
        //     int j = StdRandom.uniform(i + 1);
        //     String temp = words[i];
        //     words[i] = words[j];
        //     words[j] = temp;
        // }
        // StdOut.println("随机选取的单词：" + words[0]);
    }
}

内容的提问来源于stack exchange，提问作者DTJ