我正在 Coursera 上观看 Robert Sedgewick 的视频，目前正在观看 Shuffle 视频。他展示了一个“写得不好”的在线扑克洗牌代码（它还有一些其他错误，我已将其删除，因为它们与我的问题无关）这就是算法的工作原理：
for(int i = 0; i < N; i++)
int r = new Random().nextInt(53);
swap(cardArray, i, r);
它会迭代所有卡片一次。每次迭代都会生成一个随机数，并将第 i 张卡与第 r 张卡交换。很简单，对吧？
虽然我理解算法，但我不理解他的概率计算。他说，因为 Random 使用 32 位种子（或 64 位，似乎并不重要），所以这仅限于 2^32 种不同的排列。
他还说 Knuth 的算法更好（与 for 循环相同，但选择 1 和 i 之间的数字），因为它给你 N！排列。
我可以同意Knuth的算法计算。但我认为第一个（应该是错误的）应该有 N^N 不同的排列。
塞奇威克是错的还是我遗漏了一个事实？
塞奇威克的解释方式对我来说似乎非常奇怪和迟钝。
想象一下，您的一副牌只有 3 张牌，并应用了所示的算法。
交换第一张牌后，将有 3 种可能的结果。在第二次之后，9。在第三次交换之后，27。因此，我们知道使用交换算法，我们将有 27 种不同的可能结果，其中一些结果将与其他结果重复。
现在，我们知道 3 张牌有 3 * 2 * 1 = 6 种可能的排列方式。然而，27 不能被 6 整除。因此，我们知道，即使不计算它们是什么，某些排列也会比其他排列更常见。因此，交换算法不会导致6种可能性之间的概率相等，即它会偏向于某些排列。
同样的逻辑也适用于 52 张牌的情况。
我们可以通过查看三张牌情况下的结果分布来调查哪种安排是首选，它们是：
1 2 3 出现 5 次
1 3 2 出现 5 次
2 1 3 出现 4 次
2 3 1 出现 4 次
3 1 2 出现 4 次
3 2 1 出现 5 次
总计 27
检查这些，我们注意到需要 0 次或 1 次交换的组合比需要 2 次交换的组合出现的次数更多。一般来说，组合所需的交换次数越少，这种可能性就越大。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
