Java.util.Collection.Shuffle 使用种子随机时不产生随机结果

Question

给定以下代码：

        List<Integer> consensusGroupOrder = new ArrayList<>();

        for (int i = 0; i < numberOfItems; i++) {
            consensusGroupOrder.add(i + 1);
        }

        Collections.shuffle(consensusGroupOrder, new Random(seed));

        int count = 1;

        Map<Integer, Integer> returnValue = new HashMap<>();

        for(Integer group: consensusGroupOrder) {
            returnValue.put(count++, group);
        }

当我将 numberOfItems 设置为 4 并以 1 的种子开始时，当将 returnValue 转储为 Json 时，我得到：

{
  "1": 4,
  "2": 1,
  "3": 2,
  "4": 3
}

增加种子，列表中的第四项始终为 3。种子 = 5:

{
  "1": 4,
  "2": 1,
  "3": 2,
  "4": 3
}

种子 = 10：

{
  "1": 2,
  "2": 4,
  "3": 1,
  "4": 3
}

种子 = 255:

{
  "1": 1,
  "2": 2,
  "3": 4,
  "4": 3
}

我正在随机播种，因为我需要根据种子确定结果，但为什么第 4 项总是 3？只有当seed = 256时，第四项才会改变。

我发现了这个问题，答案是在随机数上调用 nextInt()：Collection.shuffle with seeded Random - anomaly with List of size 16

感觉就像在使用 Random 之前调用 nextInt() 只是将问题沿着种子值踢了一会儿，然后又会在某处发生？

Answer 1

你真倒霉！将非 3 洗牌到最后位置的第一个正种子是 256。自己尝试使用此代码找出将非 3 洗牌到最后位置的前 10 个种子。

public class Main {

  public static void main(String[] args) {
    IntStream.range(0, 1_000_000).filter(Main::lastPositionIsNot3).limit(10).forEach(System.out::println);
  }

  public static boolean lastPositionIsNot3(long seed) {
    List<Integer> consensusGroupOrder = new ArrayList<>();

    int numberOfItems = 4;
    for (int i = 0; i < numberOfItems; i++) {
      consensusGroupOrder.add(i + 1);
    }
    Collections.shuffle(consensusGroupOrder, new Random(seed));

    return consensusGroupOrder.get(3) != 3;
  }
}

种子256，顺序为1,3,2,4

请注意，shuffle 保证“假设随机源是公平的，所有排列都以相同的可能性发生。” java.util.Random 和 shuffle 都不能保证必须有一对种子，它们都低于 256，这将以最后一个元素不同的方式对列表进行洗牌。

如果您查看更大的样本量，例如从 0 到 100 万的所有种子，并计算有多少那些种子没有产生 3 作为它们的最后一个元素，你会得到一个更预期的结果：

long count = IntStream.range(0, 1_000_000).filter(Main::lastPositionIsNot3).count();
System.out.println(count);

这为我打印了 750,404。大约四分之三的种子没有将 3 洗牌到最后，这是预期的。实际数量比我们预期的多 404 个种子 (0.05%)。如果您检查整个种子范围（0 到 2^48-1）并计算其中有多少次将非 3 洗牌到最后，我希望这个百分比会更低。

简而言之，前 256 个种子的样本量太小，无法说明种子的分布。

Answer 2

我刚刚接受了作者在 Collection.shuffle with seeded Random - anomaly with List of size 16 上提出的解决方法：

        List<Integer> consensusGroupOrder = new ArrayList<>();

        for (int i = 0; i < numberOfItems; i++) {
            consensusGroupOrder.add(i + 1);
        }

        Random r = new Random(seed);
        r.nextInt();

        Collections.shuffle(consensusGroupOrder, r);

        int count = 1;

        Map<Integer, Integer> returnValue = new HashMap<>();

        for(Integer group: consensusGroupOrder) {
            returnValue.put(count++, group);
        }

Java.util.Collection.Shuffle 使用种子随机时不产生随机结果

Java.util.Collection.Shuffle not producing random results when using a seeded Random

java

random

collections