Knuth 洗牌算法

给定一个数组 \(a_1,\cdots,a_n\)，设计一个公平的洗牌算法。

洗牌即随机生成给定数组所有元素的一个排列，这样的排列一共有 \(n!\) 个，因此算法的目标是 等概率 地给出其中的一个。对于任意一个元素都能 独立且等概率 地放置在任意一个位置上。

算法

从后向前遍历数组，对于当前元素 \(a_i\)，从 \(a[1,\cdots,i]\) 中随机选取 \(a_j\)，和 \(a_i\) 交换。

for i from n to 1:
    j = random(1,i)
    swap(a[i], a[j])

现在证明，任意元素 \(a\) 出现在位置 \(p\) 上的概率 \(P(a,p)=\frac{1}{n}\).

1. 首先，当 \(i\) 从 \(n\) 遍历到 \(p+1\) 时，\(a\) 均未被选中，其概率为 \(\prod_{p+1\le i\le n}\frac{i-1}{i}=\frac{p}{n}\);
2. 当 \(i=p\) 时，\(a\) 被选中并替换到位置 \(p\) 上，概率为 \(\frac{1}{p}\);
3. 综上可知，\(P(a,p)=\frac{p}{n}*\frac{1}{p}=\frac{1}{n}\).

显然地，算法的时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\).

另一种表示

每次从数组中随机不放回地抽取一个元素，生成的排列即是洗牌的一个结果。

b[1,···,n] // 存放结果
k=1
for i from n to 1:
    j = random(1,i)
    b[k++]=a[j]
    remove(a[j])

算法的时间复杂度和空间复杂度均为 \(O(n)\).

参考

• Fisher–Yates shuffle - Wikipedia