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

Question

Collections.shuffle() 向后遍历 Collection 的每个索引，然后将其与运行dom 索引 包括或之前 交换。我想知道为什么，所以我尝试做同样的事情，但是用 any 运行dom 索引交换 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 随机播放。这是一种分布更均匀的洗牌形式，不会重新洗牌，这与您的算法相反。

您的算法所做的（也称为 朴素实现 ）是它会随机选择任何数组索引并将其洗牌，这意味着它选择的可能性很高之前已经改组的相同索引。

Fisher-Yates 随机播放（也称为 Donald Knuth 随机播放）是一种无偏算法，它以相同的概率随机播放数组中的项目。它避免了 'moving' 相同对象两次的机会。

Here's a good explanation of the Fisher Yates Shuffle 来自 Coding Horror 的 Jeff Atwood，他讨论了随机洗牌与 Fisher Yates 洗牌的简单实现。

另请参阅有关 Java 实施的 SO 问题。 It mentions what you asked. 如果您愿意，也可以查看源代码，如此处所述。我在前 5 个链接中通过谷歌搜索 Collections.shuffle() 找到了它。

为了进一步讨论这个问题，与简单的实现相比，使用 Fisher-Yates 洗牌总是一个好主意，特别是在需要更高级别随机性的实现中（例如洗牌扑克牌）以避免引入赔率和不公平的比赛。如果基于我们天真的实现来实现机会游戏，那将不是一件好事，因为偏见会导致您观察到的结果，其中相同的排列似乎出现得更多经常比其他人。

最后，正如用户@jmruc 提到的，这是一个关于可视化算法的非常好的教程，它包含 Fisher-Yates shuffle 以及其他算法，所有这些都呈现得很漂亮。如果您更喜欢视觉化，可能会帮助您理解这些概念：Visualizing Algorithms by Mike Bostock

Answer 2

这是 Fisher-Yates 的另一种解释。

考虑以下方法：

有两个列表，A和B。最初，所有元素都在列表 A 所以列表 B 为空。
每一步：

从当前列表 A 中的元素中以均匀概率选取。

排列列表 A 使所选元素成为最后一个元素。

从列表 A 中删除最后一个元素并将其附加到列表 B。
当列表 A 为空时，return 列表 B.

我发现此算法易于理解和可视化。

在第一步中选择给定项目的概率是 1/n。给定项目在第二步中被选中的概率是其在第一步中未被选中的概率 (n-1)/n 乘以其在第二步中被选中的概率，因为它仍在列表 A 中，1/(n-1)。该产品是 1/n。

同样，它有 ((n-1)/n)*((n-2)/(n-1)) = (n-2)/n 的概率在两个项目被移动后仍然在列表 A 中，因此有 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.

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

Why does the Collections.shuffle() algorithm work better than my implementation

java

shuffle