为何Knuth洗牌的随机数范围是0到i而非0到N-1？

Knuth洗牌（又称Fisher-Yates洗牌）的核心是生成完全公平的随机排列——每个元素出现在任意位置的概率严格为1/N。随机数范围随循环变量i动态调整为0到i，而非固定0到N-1，是实现公平性的必然要求，从概率和算法逻辑两方面可以清晰解释：

1. 概率公平性的核心推导 #

假设数组长度为N，我们逐个确定每个位置的元素：

• 当处理第i个位置（从0开始计数）时，前面0到i-1的位置已经固定了i个不重复的元素，剩余i+1个未确定位置的元素（包括当前i位置的元素）。
• 要让每个剩余元素有均等机会被放到i位置，随机数必须覆盖这i+1个元素的索引，也就是0到i。此时每个元素被选中的概率是1/(i+1)，最终推导下来，每个元素出现在任意位置的概率恰好是1/N：
  元素x出现在位置k的概率 = 前k次未被选中的概率 × 第k次被选中的概率
  = (N/N) × ((N-1)/N) × ... × ((N - k)/N) × (1/(N - k)) = 1/N

如果固定选0到N-1的随机数，会导致已固定位置的元素被重复选中，破坏概率平衡。比如N=3时，错误算法生成的某些排列概率会高于1/6，而另一些低于1/6，完全失去公平性。

2. 算法的“逐步锁定”逻辑 #

Knuth洗牌的本质是不重复地为每个位置分配元素：

• 遍历到i位置时，我们需要从“还没被安排到前面位置的元素”里随机选一个放到当前位置。
• 随机数范围0到i，正好对应这些剩余元素的索引（从前往后遍历时，剩余元素是0到i）。选中目标索引后，将其与i位置的元素交换，这样i位置的元素就被锁定，继续处理下一个位置。
• 这种逻辑避免了重复选择已固定的元素，确保每个元素只会被安排到一个位置，同时保证了选择的随机性。

3. 错误逻辑的反例 #

如果每次都选0到N-1的随机数，会出现元素被反复交换的问题：

• 比如某个元素已经被放到位置0，处理位置1时又选中它，会把它移到位置1，导致位置0的元素被替换。
• 最终生成的排列不是均匀分布的，比如N=2时看似结果没问题，但N=3时，某些排列出现的概率会是4/27，而正确算法的每个排列概率都是6/27=1/6，差异明显。

内容的提问来源于stack exchange，提问作者Ali Abbasifard