Collections.shuffle()
向后遍历Collection
的每个索引,然后将其与随机索引交换,该随机索引包括或在其之前。我想知道为什么,所以我试着做同样的事情,但用交换Collection
中的任何随机索引。
以下是Collections.shuffle()代码的shuffling部分:
for (int i=size; i>1; i--)
swap(arr, i-1, rnd.nextInt(i));
这是我的算法:
Random r = new Random();
for (int i = 0; i < a.size(); i++) {
int index = r.nextInt(a.size());
int temp = a.get(i);
a.set(i, a.get(index));
a.set(index, temp);
}
当我在同一个ArrayList
上运行了一百万次时,我发现Collections.shuffle()
的分布比我的代码均匀得多。此外,当在上运行我的代码时
[0,1,2,3,4]
以下排列似乎一直是最常见的:
[1,0,3,4,2]
[1,2,3,4,0]
[1,2,0,4,3]
[0,2,3,4,1]
[1,2,3,0,4]
有人能解释一下原因吗?
Collections.Shuffle()
执行Fisher Yates洗牌。这是一种分布更均匀的洗牌形式,与你的算法相比,它不会重新洗牌之前可能已经洗牌的东西。
您的算法(也称为天真实现)的作用是,它将随机选择任何数组索引并对其进行混洗,这意味着它很有可能选择之前已经混洗过的相同索引。
Fisher-Yates洗牌(也称为Donald Knuth洗牌)是一种无偏算法,它以同样可能的概率洗牌数组中的项目。如果它两次"移动"相同的对象,它就避免了这种机会。
以下是我们自己的Jeff Atwood在《编码恐怖》中对Fisher Yates洗牌的一个很好的解释,他讨论了随机洗牌与Fisher Yates Shuffle的天真实现。
另请参阅关于Java实现的SO问题。它提到了你的要求。如果您愿意,您也可以查看源代码,如前所述。我通过谷歌搜索前5个链接中的Collections.shuffle()
找到了它。
为了进一步讨论这一点,与简单的实现相比,使用Fisher Yates洗牌总是一个好主意,尤其是在需要更高随机性水平的实现中(如洗牌扑克),以避免引入赔率和不公平的游戏。如果机会游戏是基于我们天真的实现来实现的,那将不是一件好事,因为偏见导致了你所观察到的,在那里,相同的排列似乎比其他排列更频繁地出现。
最后,正如用户@jmruc所提到的,这里有一个关于可视化算法的非常好的教程,它包含Fisher Yates shuffle以及其他算法,所有这些都非常漂亮。如果你更像一个可视化者,可能会帮助你理解这些概念:Mike Bostock 的可视化算法
这是对费雪-耶茨的另一种解释。
考虑以下方法:
- 有两个列表,A和B。最初,所有元素都在列表A,因此列表B为空
-
每一步:
从当前列表A中的元素中以均匀概率选取。
对列表A进行静音处理,使所选元素成为最后一个元素。
从列表A中删除最后一个元素,并将其附加到列表B中。
- 当列表A为空时,返回列表B
我发现这个算法很容易理解和可视化。
给定项目在第一步中被选择的概率是1/n
。给定项目在第二步上被选择的概率是其在第一步上未被选择的可能性(n-1)/n
,乘以其在第二步骤上被选择(如果它仍在列表a上)的概率1/(n-1)
。那个产品是1/n
。
类似地,它具有在移动了两个项目之后仍然在列表A上的概率((n-1)/n)*((n-2)/(n-1)) = (n-2)/n
,并且因此具有作为所选择的第三个项目的1/n
概率。
通常,在已经选择了k
项目之后仍然在列表A上的概率是((n-1)/n)*((n-2)/(n-1))*...*((n-k)/(n-k+1)) = (n-k)/n
。给定项目仍在列表A上,在下一步骤上被选择的概率为1/(n-k)
,因此当列表A具有(n-k)
项目时,在步骤上被无条件选择的概率是((n-k)/n)*(1/(n-k)) = 1/n
。
Fisher Yates就是这样一种算法,它有两个列表,它们的总长度总是n
,连接在一个数组中。在每一步中,它以均匀的概率从列表A中选择一个元素,排列列表A以使该元素与列表B相邻,然后移动边界,使其从列表A元素变为列表B的最近添加的元素。