为什么Collections.shuffle()算法比我的实现更好

Question

Collections.shuffle()经过一个Collection向后的每个索引,然后用随机索引交换它,包括或之前.我想知道为什么,所以我尝试做同样的事情,但交换任何随机索引Collection.

这是Collections.shuffle()代码的混乱部分:

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);
}

我发现Collections.shuffle()当我同时运行两ArrayList百万次时,我的代码分布比我的代码更均匀.此外,在运行我的代码时:

[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]

有人可以解释一下原因吗？

Answer 1

Collections.Shuffle()做了费雪耶茨洗牌.这是一种更均匀分布的改组形式,与你的算法相反,它不会重新洗牌之前已经改组过的东西.

你的算法所做的事情(也就是所谓的天真实现)是它将随机选择任何数组索引并将其随机转移,这意味着它很有可能选择之前已经洗牌过的相同索引.

Fisher-Yates shuffle(也称为Donald Knuth Shuffle)是一种无偏的算法,以同样可能的概率对阵列中的项进行混洗.它避免了两次"移动"相同物体的机会.

这是我们自己的Jeff Atwood在Coding Horror 中对Fisher Yates Shuffle的一个很好的解释,他讨论了随机shuffle与Fisher Yates shuffle的天真实现.

另请参阅关于Java实现的这个问题.它提到了你的要求.如果您愿意,也可以查看源代码,如前所述.我通过Googling Collections.shuffle()在前5个链接中找到了它.

为了将来讨论这个问题,与天真的实现相比,使用Fisher-Yates shuffle总是一个好主意,特别是在需要更高级别随机性的实现中(例如随机扑克牌),以避免引入赔率和不公平的游戏.如果根据我们天真的实现实现机会游戏,那将是一件好事,因为偏见导致你观察到的东西,其中相同的排列似乎比其他排列更频繁地出现.

最后,正如用户@jmruc所提到的,这是一个关于可视化算法的非常好的教程,它包含了Fisher-Yates shuffle以及其他算法,所有算法都精美呈现.如果您更像是一个可视化工具,可以帮助您绕过概念:Mike Bostock可视化算法