Knuth Shuffle 洗牌算法

Knuth Shuffle 是一个 公平 的洗牌算法

代码讲解

1
2
for (int i = n - 1; i >= 0; i--)
  swap(array[i], array[random() % (i + 1)])

算法逻辑：i 从后向前，每次随机一个 [0…i] 之间的下标为 j，然后交换 array[i] 和 array[j] 的值。

要注意选择 j 时，选择的范围是 [0..i]，是一个 左闭右闭区间，否则无法保证其 公平性，因为：
如果选择 j 时用的是 [0…i) 的左闭右开区间，那么对于第 5 个元素 m，与其进行交换的元素只会出现在 [0…5)，也就是前 4 个元素，那么第 5 个元素一定不会出现在第 5 个位置，也就是第 5 个元素出现在第 5 个位置的可能性为 0，而不是 $\frac{1}{n}$

公平性

公平性定义

  • 第一种定义：如果有 n 个元素，最终排列的可能性一共有 n! 个，公平的洗牌算法，应该能等概率地给出这 n! 个结果中的任意一个
  • 第二种定义：每一个元素都能等概率地出现在每一个位置，也就是每一个位置都能等概率地放置每个元素，也就是对于 n 个元素，任意元素 m 出现在第 i 个位置的可能性是 $\frac{1}{n}$

公平性验证

一个元素 m，在 第 i 次选择中（先不考虑前 i - 1 次都没有选中元素 m 的概率），没有选中的可能性是 $\frac{n - i}{n -i + 1}$，选中的可能性是 $\frac{1}{n - i + 1}$。
所以m 被放入第 i 个位置的概率 P 为 前 i - 1 个位置没有选中 m 的概率 $\times$ 第 i 个位置选中 m 的概率，所以元素 m 出现在位置 i 的可能性即：
$$P = \frac{n - 1}{n} \times \frac{n - 2}{n - 1} \times … \times \frac{n - i + 1}{n - i + 2} \times \frac{1}{n - i + 1} = \frac{1}{n}$$

加密运用

在 i 从后向前遍历时，选择出一个 [0…i] 区间内的 j，交换 array[i] 与 array[j] 的值，将 j 的值和 i 关联起来，也就是 $j = f(i)$，可以将打乱后加密的数组逆向成原来的样子

1
2
3
4
5
6
7
8
9
10
11
// 加密
for (int i = n - 1; i >= 0; i--) {
  int j = f(i) % (i + 1);
  swap(array[i], array[j]);
}

// 解密
for (int i = 0; i <= n - 1; i++) {
  int j = f(i) % (i + 1);
  swap(array[i], array[j]);
}