洗牌算法分析

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

问：给定一个不同整数的数组，给出一个算法来随机 对整数重新排序，以便每个可能的重新排序都是相等的 可能。换句话说，给定一副牌，你如何洗牌 使得任何牌的排列都是同样可能的？

好答案：按顺序遍历元素，将每个元素与 数组中不早于出现的随机元素 元素。这需要 O(n) 时间。注意，有几种可能 这个问题的解决方案，以及几个好看的答案 那些是不正确的。例如，对上面的稍作修改 算法，其中一个元素与任意元素进行交换 大批不以相同的概率给出每个重新排序.

我想知道的是，为什么与使用 Knuth shuffle（已描述）相比，将每个元素与数组中的任何其他元素交换不会产生良好的洗牌效果。另外，Knuth shuffle 是如何以等概率选择值的？任何数学或证明都将受到高度赞赏。

最简单的证明该算法不会产生均匀随机排列

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

它产生 27 种可能的结果，但只有 3 种！ = 6 种排列。由于 6 不能整除 27，所以一定有一些排列被选取太多，而另一些排列被选取太少。

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

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