algorithm - 洗牌算法分析

Question

我遇到了以下对洗牌算法的分析:

Q: Given an array of distinct integers, give an algorithm to randomly reorder the integers so that each possible reordering is equally likely. In other words, given a deck of cards, how can you shuffle them such that any permutation of cards is equally likely?

Good answer: Go through the elements in order, swapping each element with a random element in the array that does not appear earlier than the element. This takes O(n) time. Note that there are several possible solutions to this problem, as well as several good‐looking answers that are incorrect. For example, a slight modification to the above algorithm whereby one switches each element with any element in the array does not give each reordering with equally probability.

我想知道的是为什么将数组中的每个元素与任何其他元素切换不会产生良好的洗牌，而不是使用 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 算法是正确的？这需要多一点洞察力。您可以通过归纳证明第一个项目以正确的概率被选中(每个项目成为第一个的可能性相同)，然后证明归纳步骤在您通过循环前进时成立，第二个，第三个等项目是也以正确的概率从数组的剩余部分中选择。