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

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

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

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

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 个数即为满足要求的抽样。

参考代码：

// 构造长度为 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]

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

参考