Java(或任何语言)概率中的随机混乱

Question

所以,我正在观看Robert Sedgewick关于Coursera的视频,而我现在正在洗牌.他正在为在线扑克显示一个"写得不好"的洗牌代码(它有一些其他的错误,我已经将其删除,因为它们与我的问题无关)这就是算法的工作原理:

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的算法更好(循环相同,但选择1和i之间的数字),因为它给你N!排列.

我同意Knuth的算法计算.但我认为在第一个(应该是错误的)上应该有N ^ N个不同的排列.

塞奇威克错了还是我错过了一个事实？

Answer 1

塞奇威克的解释方式对我来说似乎非常奇怪和迟钝。

想象一下，您的一副牌只有 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 次交换的组合出现的次数更多。一般来说，组合所需的交换次数越少，这种可能性就越大。