洗牌算法分析

Question

洗牌算法分析

13

我看到了以下有关洗牌算法的分析：

问题：给定一个不同整数的数组，请提供一种算法来随机重新排列这些整数，使得每种可能的重排都是等可能的。换句话说，如果给你一副牌，你如何洗牌，使得牌的任何排列都是等可能的？

完好的答案：按顺序遍历数组中的元素，将每个元素与数组中不早于该元素出现的位置上的随机元素进行交换。这需要 O(n) 的时间。请注意，此问题有几种可能的解决方案，以及几个看起来不错但实际上是错误的答案。例如，稍微修改上述算法，使每个元素与数组中的任何元素交换不能给出每种重新排序的等概率性。

我想知道的是，为什么将每个元素与数组中的任何其他元素交换不能产生良好的洗牌效果，相比使用 Knuth 洗牌算法（已描述）而言。另外，Knuth 洗牌算法如何选择具有相等概率的值？如果有任何数学或证明，将不胜感激。

- OckhamsRazor

4个回答

6

考虑一个包含三个元素的列表。它有以下可能状态和相关概率：

1 [a, b, c] (0)

在第一次洗牌操作中，a 有 1/3 的概率与任何元素交换，因此可能的状态和相关概率如下所示：

From (0)
1/3 [a, b, c] (1)
1/3 [b, a, c] (2)
1/3 [c, b, a] (3)

在第二次洗牌操作中，同样的事情再次发生，只不过是针对第二个插槽，因此：

From (1) ([a, b, c])
1/9 [b, a, c] (4)
1/9 [a, b, c] (5)
1/9 [a, c, b] (6)
From (2) ([b, a, c])
1/9 [a, b, c] (7)
1/9 [b, a, c] (8) 
1/9 [b, c, a] (9)
From (3) ([c, b, a])
1/9 [b, c, a] (10)
1/9 [c, b, a] (11)
1/9 [c, a, b] (12)

在第三次洗牌操作中，相同的事情发生在第三个位置上，因此：

From (4) ([b, a, c])
1/27 [c, a, b] (13)
1/27 [b, c, a] (14)
1/27 [b, a, c] (15)
From (5) ([a, b, c])
1/27 [c, b, a] (16)
1/27 [a, c, b] (17)
1/27 [a, b, c] (18)
From (6) ([a, c, b])
1/27 [b, c, a] (19)
1/27 [a, b, c] (20)
1/27 [a, c, b] (21)
From (7) ([a, b, c])    
1/27 [c, b, a] (22)
1/27 [a, c, b] (23)
1/27 [a, b, c] (24)
From (8) ([b, a, c])
1/27 [c, a, b] (25)
1/27 [b, c, a] (26)
1/27 [b, a, c] (27)
From (9) ([b, c, a])
1/27 [a, c, b] (28)
1/27 [b, a, c] (29)
1/27 [b, c, a] (30)
From (10) ([b, c, a])
1/27 [a, c, b] (31)
1/27 [b, a, c] (32)
1/27 [b, c, a] (33)
From (11) ([c, b, a])
1/27 [a, b, c] (34)
1/27 [c, a, b] (35)
1/27 [c, b, a] (36)
From (12) ([c, a, b])
1/27 [b, a, c] (37)
1/27 [c, b, a] (38)
1/27 [c, a, b] (39)

将类似项合并，我们得到：

4/27 [a, b, c] From (18), (20), (24), (34)
5/27 [a, c, b] From (17), (21), (23), (28), (31)
5/27 [b, a, c] From (15), (27), (29), (32), (37)
5/27 [b, c, a] From (14), (19), (26), (30), (33)
4/27 [c, a, b] From (13), (25), (35), (39)
4/27 [c, b, a] From (16), (22), (36), (38)

这显然是不均匀的。

只从尚未选择的元素中进行随机排序的洗牌方法是正确的。以下是证明:

考虑你有一个元素袋子。如果你从袋子里随机挑选并将结果元素放入列表中，那么你会得到一个随机排序的列表。这本质上就是只与尚未选择的元素交换所做的事情（可以将放置东西的列表视为列表的开头，将袋子视为可以与之交换的列表的末尾）。

- Mankarse

3

首先，虽然所描述的算法非常接近，但它并不完全是O(n)，而应该是O(n*log(n))。原因在于：第一次交换需要从n个元素中选择，然后是n-1...2。但是从n个元素中进行选择的复杂度实际上应该是log(n)，因为您必须生成log(n)个随机位。

rrenaud提出了一个很好的论点，即“坏”算法不均匀，因此我将尝试证明“好”算法是均匀的。每一步您都可以从n、n-1、...、1个选择中选择一个，因此最终可能有n!种选择。由于有n!种排列列表的方式，如果每个排列都可以通过至少一个选择序列达到，则每个排列都可以通过恰好一个选择序列达到。因此，为了显示它是均匀的，我们只需要证明对于给定的一些可能的排序，我们可以通过一系列选择来达到它。

现在问题看起来很简单。假设您从以下开始：

a b c d e 您想得到：

b c d e a

把光标放在第0个元素上。您应该与哪个元素交换？与b交换，因为您想将其移动到第0个位置。现在继续。在每个步骤中，“在您后面”的所有元素都在正确的位置上，因此当您到达末尾时，所有元素都在正确的位置上。

- Owen

2

谢谢Owen。不幸的是，我不同意你的第一个说法。该算法的复杂度为O(n)，因为从n个元素中进行选择的复杂度为O(1)，由于您依靠数组的连续形式在数组索引范围内选择随机元素。假设随机数生成器以O(1)生成数字，则算法运行时的复杂度为O(n)。另一点：“由于有n！种对列表进行排序的方法”实际上应该是“由于有n！种对列表进行置换的方法”。你所说的和你想表达的有很大的区别。但还是感谢你的帮助。 - OckhamsRazor

1

@OckhamsRazor 如果你需要从n个元素中进行选择，那么你至少需要log2(n)个随机位来做出决策。 - Owen

1

Owen面临的问题是生成随机数不是O(1)。例如，一些rand()实现具有32K（16位）的RAND_MAX。因此，如果您想在2^16和2^32个项目之间进行洗牌，则需要调用2次rand，并随着数字增长而逐渐增加。（如果需要确保结果真正无偏差，由于模剪辑，这更加棘手:(但您可能愿意忽略该偏差。） - Michael Anderson

1

所以随机数生成不是O(1)吗？好的，那么Owen可能是正确的。此外，你提到了“至少有一个选择序列”。虽然我知道你的意思，但措辞有误导性。如果有x个序列可以得到一个排序，那么对于所有排序来说，这一点必须成立才能将分布视为均匀的。你的措辞暗示着只需要最少1个序列就可以得到某个排序，并且不管得到其他排序的方式有多少种都没有关系。除此之外，我喜欢你的回答。 - OckhamsRazor

2

@OckhamsRazor 那是个好观点，我表达得有点不清楚。我的意思是，既然有n！种选择和n！种排序方式，如果每种排序方式都至少有一个选择，那么每种排序方式都恰好有一个选择。如果您能提出重新措辞的建议，我会进行编辑。 - Owen

显示剩余7条评论

1

首先，注意到 Knuth 的方法必须是均匀随机的，因为这本质上等同于从堆 A 中抽取随机卡牌，并通过以随机顺序放置它们来形成堆 B。这必须是均匀随机的。

要看出另一种方法不好，只需证明不同结果的数量排除了有均匀结果的可能性。在 1 到 52 之间选择 52 个随机整数有 52^52 种方式。然而，这些整数有 52! 种排列方式。52! 有 47 作为因子，而 52^52 没有；因此，52! 不能均匀地分割 52^52。这意味着至少有一个排列具有比其他排列更多的结果...为了看到这一点，请尝试平均分配结果，直到用完。由于结果的数量不是排列数量的倍数，因此您无法给每个人相同的数量。换句话说，如果你把所有糖果都送出去，你就不能把 12 个糖果均匀地分给 5 个孩子。同样的原理。

- Patrick87

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rob Neuhaus · Accepted Answer

这个算法不能产生均匀随机排列的最简单证明。

for (int i = 0; i < 3; ++i) {
   swap(a[i], a[rand() % 3]);
}

它生成27种可能的结果，但只有3！= 6种排列方式。由于6不能整除27，因此必须存在某些排列被选中过多，而其他一些排列被选中过少。

为什么O(n)算法是最优的？随机洗牌需要有时触及每个输入（以更改它们），因此任何最优算法都需要至少进行O(n)的工作。

为什么Knuth算法是正确的？这需要更深入的理解。您可以通过归纳证明第一项以正确的概率被选择（每个项目被选择的可能性相等），然后证明在通过循环前进时保持归纳步骤成立，即剩余数组的第二、第三等项也从中以正确的概率被选择。