Java（或任何语言）概率中的随机洗牌
Random Shuffling in Java (or any language) Probabilities
所以，我正在 Coursera 上观看 Robert Sedgewick 的视频，目前正在洗牌。他展示了一个 "poorly written" 在线扑克洗牌代码（它还有一些其他错误，我已经删除了这些错误，因为它们与我的问题无关）算法是这样工作的：
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 个不同的排列。
Sedgewick 错了还是我漏掉了一个事实？
由于随机数生成器生成的数字序列由种子唯一确定，因此该论点是正确的 - 但它也适用于 Knuth 算法以及任何其他洗牌算法：如果 N！ > 2^M（其中N是牌的数量，M是种子中的位数，一些永远不会生成排列。但即使种子足够大，算法之间的实际区别在于概率分布：the first algorithm does not produce an uniform probability for the different permutations, while Knuth's does (assuming that the random generator is "random" enough). Note that Knuth's algorithm is also called the Fisher-Yates shuffle.
塞奇威克当然是对的。要获得真正随机的卡片顺序，您必须首先使用一种算法，在 N！可能的排列，这意味着选择 N 之一、N-1 之一、N-2 之一等，并为每个组合产生不同的结果，例如 Fisher-Yates 算法。
其次，必须有一个内部状态大于 log2(N!) 位的 PRNG，否则它会在达到所有组合之前重复自己。对于 52 张卡，即 226 位。 32 还差得远。
对不起，我不同意 Aasmund 和 Lee Daniel 的回答。 N 元素的每个排列都可以表示为 1 和 1 和 N 之间的某个索引 i 之间的 3(N - 1) 次换位（这很容易通过对 N 的归纳来证明 - 见下文）因此，为了生成随机排列它足以生成3(N-1)个介于1和N之间的随机整数。换句话说，你的随机生成器只需要能够生成3(N-1)个不同的整数。
定理
{1, ..., N}的每一个排列都可以表示为N-1个对换的组合
证明（通过对 N 的归纳）
案例 N = 1。
{1}的唯一排列是(1)可以写成0个对换的组合（0个元素的组合就是恒等式）
CASE N = 2。（仅适用于不被上面的案例 N = 1 说服的人）
有 2 个元素 (1,2) 和 (2,1) 的两个排列。排列(1,2)是1和1的换位。排列(2,1)是1和2的换位。
归纳 N -> 案例 N + 1。
对 {1, ..., N, N+1} 进行任意排列 s。如果 s 不移动 N+1，则 s 实际上是 {1, ..., N} 的排列，可以写成索引 i,j 之间 N-1 对换的组合，其中 1<=i,j <=N.
所以我们假设s将N+1移动到K。让t在N+1和K之间进行换位。那么ts不会移动N+1（N+1 -> K -> N+1）因此 ts 可以写成 N-2 个换位的组合，即
ts = t1..tN-1.
因此，s = t1..tN-1t
由N个换位组成（N+1减一）
推论
{1, ..., N} 的每个排列都可以写成 1 和 i 之间（最多）3(N-1) 个排列的组合，其中 1<=i <=N.
证明
鉴于定理，足以证明两个索引 i 和 j 之间的任何换位都可以写成 1 和某个索引之间的 3 个换位的组合。但是
交换（i，j）=交换（1，i）交换（1，j）交换（1，i）
其中交换的串联是这些换位的组合。
Sedgewick 的解释方式对我来说似乎很奇怪和迟钝。
假设您有一副只有 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 次交换的组合出现次数更多。一般情况下，组合所需的互换次数越少，越有可能。
所以，我正在 Coursera 上观看 Robert Sedgewick 的视频，目前正在洗牌。他展示了一个 "poorly written" 在线扑克洗牌代码（它还有一些其他错误，我已经删除了这些错误，因为它们与我的问题无关）算法是这样工作的：
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 个不同的排列。
Sedgewick 错了还是我漏掉了一个事实？
由于随机数生成器生成的数字序列由种子唯一确定，因此该论点是正确的 - 但它也适用于 Knuth 算法以及任何其他洗牌算法：如果 N！ > 2^M（其中N是牌的数量，M是种子中的位数，一些永远不会生成排列。但即使种子足够大，算法之间的实际区别在于概率分布：the first algorithm does not produce an uniform probability for the different permutations, while Knuth's does (assuming that the random generator is "random" enough). Note that Knuth's algorithm is also called the Fisher-Yates shuffle.
塞奇威克当然是对的。要获得真正随机的卡片顺序，您必须首先使用一种算法，在 N！可能的排列，这意味着选择 N 之一、N-1 之一、N-2 之一等，并为每个组合产生不同的结果，例如 Fisher-Yates 算法。
其次，必须有一个内部状态大于 log2(N!) 位的 PRNG，否则它会在达到所有组合之前重复自己。对于 52 张卡，即 226 位。 32 还差得远。
对不起，我不同意 Aasmund 和 Lee Daniel 的回答。 N 元素的每个排列都可以表示为 1 和 1 和 N 之间的某个索引 i 之间的 3(N - 1) 次换位（这很容易通过对 N 的归纳来证明 - 见下文）因此，为了生成随机排列它足以生成3(N-1)个介于1和N之间的随机整数。换句话说，你的随机生成器只需要能够生成3(N-1)个不同的整数。
定理
{1, ..., N}的每一个排列都可以表示为N-1个对换的组合
证明（通过对 N 的归纳）
案例 N = 1。
{1}的唯一排列是(1)可以写成0个对换的组合（0个元素的组合就是恒等式）
CASE N = 2。（仅适用于不被上面的案例 N = 1 说服的人）
有 2 个元素 (1,2) 和 (2,1) 的两个排列。排列(1,2)是1和1的换位。排列(2,1)是1和2的换位。
归纳 N -> 案例 N + 1。
对 {1, ..., N, N+1} 进行任意排列 s。如果 s 不移动 N+1，则 s 实际上是 {1, ..., N} 的排列，可以写成索引 i,j 之间 N-1 对换的组合，其中 1<=i,j <=N.
所以我们假设s将N+1移动到K。让t在N+1和K之间进行换位。那么ts不会移动N+1（N+1 -> K -> N+1）因此 ts 可以写成 N-2 个换位的组合，即
ts = t1..tN-1.
因此，s = t1..tN-1t
由N个换位组成（N+1减一）
推论
{1, ..., N} 的每个排列都可以写成 1 和 i 之间（最多）3(N-1) 个排列的组合，其中 1<=i <=N.
证明
鉴于定理，足以证明两个索引 i 和 j 之间的任何换位都可以写成 1 和某个索引之间的 3 个换位的组合。但是
交换（i，j）=交换（1，i）交换（1，j）交换（1，i）
其中交换的串联是这些换位的组合。
Sedgewick 的解释方式对我来说似乎很奇怪和迟钝。
假设您有一副只有 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 次交换的组合出现次数更多。一般情况下，组合所需的互换次数越少，越有可能。