我发现了以下对改组算法的分析:
问:给定一组不同的整数,给出一个算法来随机重整整数,这样每个可能的重新排序都是同样可能的.换句话说,如果给出一副纸牌,你怎么能将它们洗牌以使任何牌的排列同样可能？
很好的答案:按顺序遍历元素,使用数组中的随机元素交换每个元素,该元素不会出现在元素之前.这需要O(n)时间.请注意,此问题有几种可能的解决方案,以及一些不正确的好看的答案.例如,对上述算法的略微修改,其中用数组中的任何元素切换每个元素不会给出每个重新排序具有相同的概率.
我想知道的是,与使用Knuth shuffle(描述)相比,为什么用数组中的任何其他元素切换每个元素不会产生良好的混乱.另外,Knuth如何以相同的概率选择值？任何数学或证明都非常感谢.
Rob*_*aus 20
最简单的证明该算法不会产生均匀的随机排列
for (int i = 0; i < 3; ++i) {
swap(a[i], a[rand() % 3]);
}
它是否会产生27种可能的结果,但只有3种!= 6个排列.由于6不分27,所以必须有一些排列被挑选太多,而有些被挑选得很少.
为什么O(n)算法是最优的？好吧,随机shuffle有时必须触摸每个输入(改变它们),所以任何最优算法都需要至少做O(n)工作.
为什么Knuth算法是正确的？这需要更多的洞察力.您可以通过归纳证明第一项是以正确的概率选择的(每个项目同样可能是第一项),然后证明当您在循环中前进时归纳步骤成立,第二,第三等项目是也从阵列的其余部分以正确的概率选择.
考虑一个三元素列表.它具有以下可能的状态和相关概率:
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)
这显然是不平衡的.
您只从尚未选择的元素中选择的shuffle是正确的.为证明我提出这个:
考虑一下你有一袋元素.如果您从该包中随机选择并将结果元素放在列表中,您将获得一个随机排序的列表.这基本上只与那些尚未被选中的元素进行交换(考虑将您放置的内容作为列表的开头,并将该包作为列表的尾部,可以与之交换).