面试时,遇到这么一个问题,觉得比较有意思,可惜我答得不好,特记录下。

面试官:请设计一个扑克牌发牌的程序
我:最初回答的很简单:先生成一副牌,再将牌随机打乱,然后平均分给4个数组
面试官:怎么将牌随机打乱呢?
我:Python 中有个 shuffle 函数,可以随机打乱
面试官:如果不用 shuffle 函数呢?
我:想了会儿,用随机数生成器,随机生成两张牌的索引,然后交换。
面试官:需要交换多少次?
我:懵逼+黑人问号脸。。。

后来查了下,其实这是一个经典的算法题:随机洗牌法。该算法要保证:任何一张牌,在所有的位置上的概率相同,或者说,有 N 张牌,遍历这 N 张牌,使得每张牌出现在任何位置的概率都为 1/N。具体操作如下:

这将扑克牌看做一个数组,依次遍历数组,对第 n 个元素,随机生成一个 0 到 n 之间的数 r,然后与第 r 个 个位置上的元素互换,最后生成的序列,即可满足要求。具体 python 版本实现如下:

1
2
3
4
5
6
7
import random

def shuffle_poker(poker_list):
l = len(poker_list)
for i,pk in enumerate(poker_list):
idx = random.randint(0, i)
poker_list[idx], poker_list[i] = poker_list[i],poker_list[idx]

可以看到,代码写出来十分简洁,那是不是符合要求的呢?下面我们来证明下,证明需要用到数学归纳法。

证明

先考察只有几个元素时的情况:

  1. 当 n=1 时,一个元素放在一个位置的概率为1
  2. 当 n=2 时,根据算法,第一个位置已经暂且定下位置。第二个元素只能随机两个数字,概率均为 1/2,第一个元素要么和第二个元素置换,要么位置不变,两个元素在任意这两个位置的概率都是 1/2。
  3. 当 n=3 时,根据算法,前两个元素已经暂且定下位置。我们来看看第 3 个元素在任意位置的概率是多少?根据算法,此时随机数的区间是 [0,3],任一数字的概率都为 1/3。在没有第 3 个元素和第 3 个位置时,由第 2 步知,前两个元素的任意位置概率是 1/2,那现在有3个位置,自然概率就要变化,假设第一个位置的元素值是 a,那么这个 a 现在只有两种情况,要么保持位置不变,要么和第 3 个位置交换。
    1)保持位置不变的概率是 a 在前两个位置的概率乘以新随机的数不是该位置的概率,即 1/2×(1−1/3),结果是1/3。
    2)与第 3 个位置进行交换的概率是 a 在第一个位置的概率乘以随机出第一个位置数的概率加上 a 在第二个位置的概率乘以随机出第二个位置数的概率,即 1/2×1/3+1/2×1/3,结果为 1/3。
    综上,当 n=3 时,即发完第 3 张牌后,第一个位置上的元素出现在任意位置的概率为 1/3。第二个位置也可以这么证明。

下面给出严谨证明,用到数学归纳法:
基础步骤: 当 n=1 时,第一位置元素只能随机出1,概率为1,定理成立。
归纳步骤: 当 n=k,k 个元素在任 k 个位置的概率均为$\frac {1}{k}$成立。
那么,当 n=k+1,第 k+1 位置的元素在任 k+1 个位置的概率是$\frac {1}{k+1}$,因为随机出 k+1 个数概率是一样的。前 k 个元素的概率发生了变化,任意一元素保持位置不变的概率为$\frac {1}{k}$ × ($1-\frac {1}{k+1}$),结果为$\frac {1}{k+1}$;任意一元素与第 k+1 元素进行置换的概率为$\frac {1}{k} × (\sum_{1}^{k}\frac {1}{k}× \frac {1}{k+1})$ ,结果为$\frac {1}{k+1}$,综上,前 k 个元素在任意位置的概率为$\frac {1}{k+1}$。
定理成立,证毕。

其实,上面的这种方法,就是 python random 包中的 shuffle 方法的实现,即 shuffle 方法就是用随机洗牌法来打乱一个序列的。

蓄水池算法

其实此算法可以进一步推广,即不限定元素的个数为一副牌的数量,可以认为数量非常大,我们暂把它记为序列 N,直到处理完 N 之前,我们不知道这个 N 有多大,现在需要对这样的一个序列 N 抽样,样本个数为 m,要求只遍历一遍,有什么办法保证抽样的公平性?

这就要用到蓄水池算法,这种算法过程其实和前面的随机洗牌法类似。

  1. 首先构建一个大小为 m 的数组,然后将序列前 m 个元素放入数组中。
  2. 然后从第 m+1 个元素开始,对第 k 个元素(k >= m+1),把它记为当前元素,仍然先随机生成一个 [0, k] 之间的数 r,如果 r < m,则将数组中第 r 个位置的数替换为当前元素。
  3. 遍历完该序列,数组中的 m 个数即为满足要求的抽样。

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
// 构造长度为 m 的 list
sample_list = [None] * m
l = len(sample_list)
// N 的前 m 个元素填充 list
for i in range(l):
sample_list = N[i]

// 从 m+1 个元素起,随机替换 list
for i in range(l, len(N)):
idx = random.randint(0, i)
if idx < m:
sample_list[idx] = N[i]

证明过程,依然用到数学归纳法,这里不打算给出了,有兴趣的朋友可以看下面的参考链接,或者《编程珠玑》这本书。

参考