洗牌算法分析

Question

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

Q:给定一个不同的整数数组，给出一个算法来随机地重新排序这些整数，这样每个可能的重新排序的可能性都是相等的。换句话说，如果有一副牌，你怎么能把它们洗牌，使任何牌的排列都是一样的呢？

好的答案:按顺序遍历元素，用数组中的一个不早于元素出现的随机元素交换每个元素。这需要O(n)时间。请注意，对于这个问题有几种可能的解决方案，以及一些不正确的漂亮答案。例如，对上述算法的轻微修改，即用数组中的任何元素切换每个元素，并不会给每个重排序以相同的概率。

我想知道的是，为什么使用数组中的任何其他元素切换每个元素都不会产生很好的洗牌，而不是使用Knuth洗牌(描述)。另外，Knuth洗牌是如何以相同的概率选择值的？任何数学或证明都是非常感谢的。

Answer 1

证明该算法不产生一致随机排列的最简单证明。

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

它产生27种可能的结果，但只有3！=6排列。既然6不除以27，必然会有一些排列被选得太多，而有些则被挑得很少。

为什么O(n)算法是最优的？嗯，随机洗牌有时必须触及每个输入(以改变它们)，所以任何最优算法都需要至少做O(n)工作。

为什么Knuth算法是正确的？这需要更多的洞察力。您可以通过归纳来证明第一项是以正确的概率选择的(每个项都同样可能是第一项)，然后证明当您在循环中前进时，归纳步骤仍然有效，第二项、第三项等项也是用正确的概率从数组的其余部分中选择的。

Answer 2

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

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)

这显然是不平衡的。

只从尚未被选中的元素中选择的洗牌是正确的。作为证据，我提出如下：

假设你有一袋元素。如果您从那个包中随机选择并将结果元素放在列表中，您将得到一个随机排序的列表。本质上，这就是只与那些尚未被选中的元素进行交换的方法(假设您放置东西的列表是列表的开始，而袋子是列表的尾部，可以与之交换)。

Answer 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、a

将光标放在第0元素上。你应该和哪一个交换？b，因为你想把它移到0的位置。现在进展。在每一步，所有“背后”的元素都在正确的位置，所以当你到达终点时，所有的元素都在正确的位置。