使用 Collections.shuffle 的带有两个元素的 Java 随机洗牌列表

Question

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class ShuffleList {
  public static void main(String[] args) {
    String [] file = {"1","2"};
    long seed = 3;
    ArrayList<String> fileList = new ArrayList<String>(Arrays.asList(file));
    for (int i=0; i<200; i++) {
      Collections.shuffle(fileList, new Random(seed));
      seed = seed +1;
      System.out.println(seed + "," + fileList);
    }
  }
}

输出是 200 行 [1,2]，根本不是随机洗牌。事实上，对于所有 < 4000 的种子都是如此。这是为什么？我尝试使用 3 个元素的列表，从 1 到 100 的种子使列表看起来随机。但是 2 个元素的列表有什么问题？

Answer 1

问题不在于 shuffle - 它在于带有小种子的 Random。这是一个演示的程序:

import java.util.Random;

public class Test {
    public static void main(String[] args) {
        int total = 0;
        for (int seed = 0; seed < 4000; seed++) {
            Random rng = new Random(seed);
            total += rng.nextInt(2);
        }
        System.out.println(total);
    }
}

您期望输出大约 2000 - 大约一半的 nextInt 调用应该返回 0，大约一半应该返回 1。相反，它是 4000 - 每个 调用返回 1。

使用种子 [10000, 13999) 你会得到 240 - 所以返回 0 的调用比返回 1 的调用要多得多。

使用种子 [100000, 103999) 你得到 3226 - 变得更好了......

使用种子 [1000000, 1003999) 你会得到 2105 - 好多了。

我对随机数生成器的数学知识知之甚少，无法说明为什么会发生这种情况，但看起来 java.util.Random 对于小种子来说确实有些问题。