Collections.shuffle()是否足够随机？实际的例子似乎否认了这一说法

Question

我有一个1000个唯一对象java.util.List,每个指的是一个图像,在1000 -列表中的每个图像都是独特的,现在我想重新洗牌他们,这样我可以使用的第一个20个对象,并提交给网站用户.然后,用户可以单击"Shuffle"按钮,然后从头开始再次检索1000个图像并再次呼叫shuffle().然而,似乎在1000个图像对象中,我经常在20个图像选择之间反复看到相同的图像.

有些东西似乎是错的,有什么更好的建议,建议吗？

我的代码非常简单:

List<String> imagePaths = get1000Images();
Collections.shuffle(imagePaths);

int i = 0;
for (String path: imagePaths) {
  ... do something with the path ...
  i++;
  if (i >= 20) break;
}

我知道Collections.shuffle()分布很好:例如参见http://blog.ryanrampersad.com/2012/03/03/more-on-shuffling-an-array-correctly/

然而,我只是觉得在一组20张图像中反复看到相同图像的概率应该小得多......

输入高度赞赏.

Answer 1

它的人性,看到不存在的模式.许多人认为行星和恒星中的模式可以指导他们的生活.

在PI的前1000个数字中,连续有六个9.这是否意味着PI的数字不是随机的？没有.该模式不会再出现超出您的预期.

话虽如此,Random并不是完全随机的,它会在2 ^ 48次调用后重复.(它使用48位种子)这意味着它不可能生成所有可能long或double使用它.如果你想要更多的随机性,你可以使用随机的SecureRandom.

这听起来像你想要的是这样的东西

List<String> imagePaths = new ArrayList<>();

// called repeatedly
if (imagePaths.size() <= 500) {
    imagePaths = get1000Images();
    Collections.shuffle(imagePaths);
}

for (String path: imagePaths.subList(0, 20)) {
  ... do something with the path ...
}

imagePaths = imagePaths.subList(20, imagePaths.size());

这将确保您在最近500次调用中看不到相同的图像.

Answer 2

如果你在1000中显示20张图像,那么在下一次迭代中看到20个中任何一个重复的概率约为0.34,所以你不应该对看到图像重复感到惊讶.

看到特定图像的机会仍然是千分之一,但如果你正在寻找二十张图像,则机会要高得多.

我们可以计算前20个图像中没有一个重复的概率:

 980   979         961
———— × ——— × ... × ——— ? 0.66
1000   999         981

因此,看到重复的概率是一减去这个,或大约0.34.

并且在接下来的两次迭代中看到图像重复的概率是:

1 - (0.66 × 0.66) ? 0.56

换句话说,你很可能会在接下来的两个周期中看到重复的图像.(这不包括第三个周期中重复出现的图像,只会使其更有可能.)

对于它的价值,这里有一些Java代码来进行上述计算:

float result = 1.0f;
int totalImages = 1000;
int displayedImages = 20;

for (int i = 0; i < displayedImages; i++) {
  result = result * (totalImages - displayedImages - i) / (totalImages - i);
}

System.out.println(result);

Answer 3

你的直觉对于特定的图像是正确的[你不可能一遍又一遍地看到特定的图像 ],但不是一般的图像[你可能会看到一些图像重复].这是我们自动直觉错误的概率之一......

这让我想起生日悖论,这违背直觉,并说-为一组的23人,具有相同的生日他们2的可能性为0.5,更那么直觉期待!