如何等概率地从n个数中随机抽出m个数？

方法1——等概率抽取法

我们最先想到也是最容易想到的是等概率抽取法,每次都随机在(0,n-1)之间抽取一个数，并与之前的数相比较，若相同，则继续随机生成；若不相同，则继续随机抽取，直到生成一个与之前所有生成数不同的数，将上述这样的随机生成做m次。

那么问题来了，如果m较大呢？

带来的变化是每次调用rand()生成的数与之前的数相重合的概率会变大，换句话说，我要随机取出m个的值，则调用rand()函数的次数会增多，这样的方法开销肯定会增大。

那到底开销有多大呢，我们来考察一下rand()函数的调用次数：

假设前面已经生成了x个数，要生成第x+1个数，那么：

调用1次rand()函数就成功生成该数的概率为：;

调用2次rand()函数就成功生成该数的概率为：;

.

.

.

调用n次rand()函数就成功生成该数的概率为：;

则生成第x+1数需要调用的rand()函数的期望为：

则总的调用rand()函数的期望为：

当m接近n时，近似为，所以用等概率抽取法不合适

还有另外一种更极端情况：假设n非常大，以至不确定n的具体大小，而且n还在动态增长，则此时需要用到下面的一种方法——蓄水池抽样。

方法2——蓄水池抽样

具体方法：我们先选取前m个数放入池中，然后我们每次以m/k的概率选择第k(k>m)个数a[k]，然后再在蓄水池中随机选取一个元素a[j],交换a[k]和a[j];

代码：

接下来证明：

假设当前是i+1, 按照我们的规定，i+1这个元素被选中的概率是m/i+1，也即第 i+1 这个元素在蓄水池中出现的概率是m/i+1 
此时考虑前i个元素，如果前i个元素出现在蓄水池中的概率都是m/i+1的话，说明我们的算法是没有问题的。 

对这个问题可以用归纳法来证明：m < i <=N 
1.当i=m+1的时候，蓄水池的容量为m，第m+1个元素被选择的概率明显为m/(m+1), 此时前k个元素出现在蓄水池的概率为 m/(m+1), 

很明显结论成立。 

2.假设当 j=i 的时候结论成立，此时以 m/i 的概率来选择第i个元素，前i-1个元素出现在蓄水池的概率都为m/i。 
证明当j=i+1的情况： 
即需要证明当以 m/i+1 的概率来选择第i+1个元素的时候，此时任一前i个元素出现在蓄水池的概率都为m/(i+1). 
前i个元素出现在蓄水池的概率有2部分组成, ①在第i+1次选择前得出现在蓄水池中; ②得保证第i+1次选择的时候不被替换掉 
①.由2知道在第i+1次选择前，任一前i个元素出现在蓄水池的概率都为m/i 
②.考虑被替换的概率： 
首先要被替换得第 i+1 个元素被选中(不然不用替换了)概率为 m/(i+1)，其次是因为随机替换的池子中m个元素中任意一个，所以不幸被替换的概率是 1/m，故 前i个元素(池中元素)中任一被替换的概率 = m/(i+1) * 1/m = 1/(i+1)，则(池中元素中)没有被替换的概率为: 1 - 1/(i+1) = i/(i+1)
综合① ②,通过乘法规则 
得到前i个元素出现在蓄水池的概率为 m/i * i/(i+1) = m/(i+1) 
故证明成立

1. 整数数组的前m个直接存下来。
2. 用一个计数器保存当前正在处理的请求是第几个，比如n
3. 对于从m+1开始的新请求，以m/n的概率选择保存，并同从已保存的m个请求中随机选出的一个进行交换。

细说就是，

• 对于第m+1个请求，以m/(m+1)的概率选择留下，如果留下了则从已保存的m个请求中随机选出一个，同它交换;
• 对于第m+2个请求，以m/(m+2)的概率选择留下，如果留下了则从已保存的m个请求中随机选出一个，同它交换;
• 对于第m+3个请求，以m/(m+3)的概率选择留下，如果留下了则从已保存的m个请求中随机选出一个，同它交换;

  …

• 对于第n个请求，以m/n的概率选择留下，如果留下了则从已保存的m个请求中随机选出一个，同它交换

//假设这n个数的序号依次为0,1,2,...,n-1,数组名为num
void knuth1(int* pNum, int m, int n)
{
    srand((unsigned int)time(0));
    for (int i=0; i<n; i++)
    {
        if (rand()%(n-i) < m)//rand()%(n-i)的取值范围是[0, n-i）
        {
            cout << pNum[i] << endl;
            m--;
        }
    }
}