随机算法中一个很基本的问题是怎么做随机抽样。比如，如何从N个元素中等概率随机抽n个出来。（n<N）
总的来说这个问题有三种解法：选择抽样、蓄水池抽样、随机洗牌。
1. 选择抽样。
理论来说，每个元素被抽中的概率应该是p=n/N。但是，如果我们对集合的每个元素都按照固定概率p选择是不是抽中它，那么结果未必那么凑巧抽中n个。
所以这个p应该是变化的。假设已经抽中了m个，那么p应该是m的函数。通过计算可得，原数组第t个元素被抽中的概率p=(n-m)/(N-t+1)。t从1开始计数。m是从0开始计数，每抽中一个就加1。
这个算法不用遍历原数组的所有元素，抽够了就中止。
2. 蓄水池抽样。
首先，我们搞一个蓄水池，size=n。然后放水装满。也就是把前n个元素扔这个池子里去。
然后，把剩余的这些元素，每个以一定概率把它扔进蓄水池中，随机替换掉池子中一个现有的。（池子中每个元素都是以相等概率被替换掉）
蓄水池装满后接下来该处理第n+1个元素，那么显然，它被抽中的概率应该是\( \frac{n}{n+1} \) 。（因为目前是从n+1个元素中抽n个）
以此类推，第t个元素被抽空的概率是：\( \frac{n}{t} \)。其中t从1开始计数，蓄水池最开始那n个元素也要被数进去。
证明： 第t个元素被扔进池子的概率是\( \frac{n}{t} \)。它被第t+1个元素替换出去的概率是 \( \frac{n}{t+1} * \frac{1}{n} = \frac{1}{t+1} \) 。所以，在经历了第t+1个元素后，它依然留在池子里的概率是 \( \frac{n}{t} * ( 1- \frac{1}{t+1}) = \frac{n}{t+1} \) 。 以此类推，直到第N个元素后，它依然在池子里的概率是\( \frac{n}{N} \)。
3. 随机洗牌
把输入的这些元素随机打乱（比如用std::random_shuffle()函数。然后取前n个。 把代码写出来仔细看看，它跟蓄水池抽样其实是完全一样的。
原文链接: http://blog.sunchangming.com/post/59682473969
|
