洗牌的正确姿势-Knuth shuffle算法

注: 在 LeetCode 上, 将该解法称为 Fisher-Yates 算法.

怎样用计算机模拟出 足够随机 的洗牌结果, 看似很简单, 但其实它比给一副乱糟糟的牌排好序可能还更难一些. 洗牌问题的描述很简单:即如何通过打乱顺序, 让一副扑克牌变成随机的排列, 而且每一种可能的排列有相同机会出现. 关键点在于 “相同机会” , 即各种随机排列是等可能的. 下面先简单介绍一个常见的错误做法, 然后看看如何改进变成Knuth 洗牌算法.

先看看一个很直接的做法(一副牌在这里用一个数组表示):对数组从头到尾扫描一遍, 扫描过程中, 每次都从整个数组随机选一个元素, 跟当前扫描到的元素交换位置.

也就是, 先拿起第一张牌, 把它跟从整副牌里随机挑出的另一张牌(把它叫做随机牌)交换位置(随机牌也可能是第一张牌自己, 这个时候就相当于不交换位置); 接着拿起第二张牌, 也把它跟随机选出的另一张牌交换位置; 一直重复直到把最后一张牌跟随机牌交换位置.

代码实现如下:

vector<int> sv(v); // v 为给定的待打乱的数组
for(int i=0; i<sv.size(); i++){
    int j = rand() % sv.size(); //这里生成的 j 位于 0 ~ size()-1 之间
    swap(sv[i], sv[j]);
}

这样随机交换之后, 每种排列出现的可能性会是等概率的吗? 假设我们的数组元素有三个: {A, B, C}, 那么最终的所有的可能排列方式就有六种, 按照要求, 这六种排列方式的出现概率应该是 相等的. 但是, 如果按照上面的方法, 最终的可能分支数为: $3\times 3 \times 3 = 27$ 种, 无法整除 6, 所以各个排列的出现概率 绝对不可能是等概率的. 分支情况如下图所示:

可以看到, 最后产生的27个结果里面, {A, B, C}, {C, A, B}, {C, B, A}都出现了4次, 而{A, C, B}, {B, A, C}, {B, C, A}都出现了5次. 也就是说有些排序出现的可能性是4/27, 有些却是5/27. 而且, 随着牌数目的增加, 这个概率的不均衡会更加严重.

从上面的分析可以看出, 要让结果够公平, 一个必要条件就是产生的分支是6的整数倍, 也就是 $N!$ 的整数倍, 为此, 我们就来介绍 Knuth Shuffle 算法. 在上述方法的基础上, 做一处修改, 就能剪去一些分支, 让分支数是N!的整数倍. 这就是Knuth洗牌算法. 代码实现如下:

vector<int> sv(v); // v 为给定的待打乱的数组
for(int i=0; i<sv.size(); i++){
    int j = i + rand() % (sv.size()-i); //这里生成的 j 只可能在 i 之后
    swap(sv[i], sv[j]);
}