1. 简单随机抽样

问题：已知一个序列长度为\(N\)，随机从中取出\(M\) (\(M < N\)) 个不重复元素。

思路：连续选取\(M\)个元素，选取第\(k\) (\(k \leq M\))个元素时，随机地在\(N\)个元素中取一个，如果取出的元素和前面\(k-1\)个元素冲突则放回重新选择，直到\(M\)个元素选择完毕。

这种思路属于“暴力破解”，时间复杂度分析如下：

假设已经选取\(k\)个元素，开始选取第\(k+1\) (\(k+1 \leq M\))个元素：

第一次随机选取达到条件的概率：\((1-\frac{k}{N})\)

第二次随机选取达到条件的概率：\((1-\frac{k}{N})\times\frac{k}{N}\)

第三次随机选取达到条件的概率：\((1-\frac{k}{N})\times (\frac{k}{N})^2\)

…

第\(m\)次选取达到条件的概率：\((1-\frac{k}{N})\times (\frac{k}{N})^{m-1}\)

那么选取第\(k\)个元素所需要的操作次数期望为：

\[\begin{aligned} E[k+1] &= (1-\frac{k}{N})\times 1+ (1-\frac{k}{n}) \frac{k}{N} \times 2 + \cdots + (1-\frac{k}{N})(\frac{k}{N})^{m-1}\times m \\ &= \frac{1-(\frac{k}{N})^{m-1}}{1-\frac{k}{N}} - (\frac{k}{N})^m \times m \\ \end{aligned} \tag{1.1}\]

上式由等差等比数列求和计算得到，当\(m \rightarrow \infty\)时：

\[E[k+1] = \frac{1}{1-\frac{k}{N}} = \frac{N}{N-k} \tag{1.2}\]

那么选取\(M\)个数所需要执行操作次数期望为：

\[\begin{aligned} E[ramdom] &= \frac{N}{N} + \frac{N}{N-1} + \frac{N}{N-2} + \cdots + \frac{N}{N-M-1} \\ &= N \times \sum_{i=0}^{M+1} \frac{1}{N-i} \\ &\approx N \times \int_{0}^{M+1} \frac{1}{N-x} dx \\ &= N \times (-\log(N-M-1) + \log N) \\ &\approx N \times (\log N - \log(N-M)) \\ \end{aligned} \tag{1.3}\]

所以时间复杂度为：\(O(n \log n)\)

2. 蓄水池算法

水池一边进水，一边出水，水池里的每一滴水会流出还是留在水池里是等概率的。

这个算法能够解决更泛化的问题：一个未知长度的链表，要求只遍历一次，随机地返回链表中一个节点。这个问题采用上面“暴力破解”的方法是不可行的，因为不知道数组（链表）的总长度，所以不能用Random函数直接生成一个随机数来选取某个值。而且这个题目还能再泛化，要求返回\(k\)个随机数，只能遍历一次的情况下，上述方法也是做不到的。

2.1 随机选择1个数

思路：当遇到第\(i\)个元素时，应该有\(\frac{1}{i}\)的概率选择该元素，\((1- \frac{1}{i})\)的概率保持原有选择。

用通俗的话说：要选择的随机数为\(ret\)。遍历第\(i\)个元素时，随机生成一个\([0， i-1]\)数字。显然，这个数字等于0的概率是\(\frac{1}{i}\)，不等于0的概率是\(1-\frac{1}{i}\)；如果等于0，则\(ret = 该数\)，否则继续遍历下一个数；重复上述操作直到遍历完成，此过程只遍历一次。最终找到的随机数是\(ret\)。整个过程像是进水和排水，每遍历一个数字就是进水，一旦进水，之前的水就有几率被排走，最终剩下在池里的水就是我们要找的随机数（池的大小是要选择的随机数个数，在该情况下为1）。

下面是该算法的证明：

欲证：该算法是随机的；

即证：每个元素被选择的概率为\(\frac{1}{n}\)。（在此题目中我们无法直接直到\(n\)的大小）

遍历到第\(i\)个元素时，它被选择的概率是\(\frac{1}{i}\)；为了保证遍历结束后选择的数字还是它，还需要以后的数字都不被选。即第\(i\)个元素最终被选择的概率计算方式为：

\[\begin{aligned} P(i) &= \frac{1}{i} \times (1-\frac{1}{i+1}) \times (1-\frac{1}{i+2}) \times \cdots \times (1-\frac{1}{n}) \\ &= \frac{1}{i} \times \frac{i}{i+1} \times \frac{i+1}{i+2} \times \cdots \times \frac{n-1}{n} \\ &= \frac{1}{n} \end{aligned} \tag{2.1}\]

即证。

2.2 随机选择\(k\)个数

下面扩展到随机选取\(k\)个元素，思路是一样的。

思路：当遇到第\(i\)个元素时，应该有\(\frac{k}{i}\)的概率选择该元素，\((1- \frac{k}{i})\)的概率保持原有选择。

用通俗的话说：要选择的随机数为\(ret[0,k-1]\)。遍历第\(i\)个元素时，随机生成一个\([0， i-1]\)的数字\(j\)。显然，\(j\)小于\(k\)的概率是\(\frac{k}{i}\)，大于等于\(k\)的概率是\(1-\frac{k}{i}\)；如果小于\(k\)，则\(ret[j] = 该数\)，否则继续遍历下一个数；重复上述操作直到遍历完成，此过程只遍历一次。最终找到的随机数是\(ret[0,k-1]\)。

下面是概率计算方式：

\[\begin{aligned} P(i) &= \frac{k}{i} \times (1-\frac{k}{i+1} \times \frac{1}{k}) \times (1-\frac{k}{i+2} \times \frac{1}{k}) \times \cdots \times (1-\frac{k}{n} \times \frac{1}{k}) \\ &= \frac{k}{i} \times \frac{i}{i+1} \times \frac{i+1}{i+2} \times \cdots \times \frac{n-1}{n} \\ &= \frac{k}{n} \end{aligned} \tag{2.2}\]

虽然每次更新选择的概率增大了\(k\)倍，但是具体选到第\(i\)个元素的概率为\(\frac{1}{k}\)。

时间复杂度为：\(O(n)\)

3. 有序随机选取

上述的方法中，随机选取\(k\)个数字确实做到了随机，但是选出来的数字是乱序的，因为\(ret[j] = 该数\)，这一步的\(j\)是随机生成的，每次都有可能将数组内部任意一个数字替换。也就是说从\([0， 1， 2， 3， 4]\)选择3个数，最终返回的数组可能为\([2, 0, 4]\)（乱序）。那么如何改进？使得选取的数字为顺序，且每个数字被选择的概率都是\(\frac{k}{n}\)。

直接上代码：

void GenerateKnuth(int n, int k){
     int t=k;
     for(int i=0; i<n; i++){
     	 if(Rand(0, n-1-i) < t){ // 以t/(n-i)的概率
	     printf("%d\n",i);
             t--;
         }
    }
}

算法的思路为： 选取第1个数时，选择概率为\(\frac{k}{n}\)；选择第2个数时，如果第1个数被选走，那么抽中概率为\(\frac{k-1}{n-1}\)，如果第1个数没有被选走，那么抽中概率为\(\frac{k}{n-1}\)。（分母都是\((n-1)\)，理解为只从后面剩下的\((n-1)\)个里面选）。 此时选取第2个数的概率为：

\[P(2) = \frac{k}{n} \times \frac{k-1}{n-1}+(1-\frac{k}{n}) \times \frac{k}{n-1} = \frac{k}{n} \tag{3.1}\]

选取第\(i\)个数时，被抽中的概率为\(\frac{k-m}{n-i+1}\)，其中\(m\)为已经抽取的个数（\(m\leq k\)），即从剩余的\((n-i+1)\)个数中选\((k-m)\)个。

时间复杂度为：\(O(n)\)

4. 基于Fisher-Yates洗牌算法

随机抽取\(k\)个元素相当于对\(n\)个元素洗牌，然后取前\(k\)个。

洗牌算法：将一个有限集合生成一个随机排序。理论上要求随机排序是等概率的。

问题：假设一副牌有\(n\)张，请问其序列有多少种可能性？

答：\(n!\)

问题：也就是说，我们需要一个算法能够理论上生成\(n!\)种结果。假设交换一副牌中的两张牌为一次洗牌（交换\(x\)和\(y\)），那么要交换多少次才能生成\(n!\)种结果呢？

答：牌的张数。

第一次洗牌：\(n\)种结果；

第二次洗牌：\(n \times (n-1)\)种结果；（因为如果交换的两张牌和第一次一样，那么等于回到最开始，没有产生新排列）

第三次洗牌：\(n \times (n-1) \times (n-2)\)；（为什么乘\((n-2)\)，可以自己想一个例子思考一下）

…

第\(n\)次洗牌：\(n!\)

但是这种方法有缺陷，漏掉牌的情况存在（概率不为0）。

Fisher-Yates算法：

for(int i=suit.length-1, i>0; i--){
    random = Random.next(1, i);
    exchange(suit[random], suit[i]);
}

思路和上述的暴力解决的办法相似：每一次都有两张牌交换，只不过有一张已确定为\(suit[i]\)，相当于再余下的\((n-i)\)中抽一张与第\(i\)张交换，所以能产生序列的总数为：\(n!\)

时间复杂度：\(O(n)\)

参考

蓄水池算法
随机抽样算法（从N取M）总结