蓄水池问题
怎样随机从N个元素中选择一个元素，你依次遍历每个元素，但不知道N多大。
将N个元素用[1、2、...、N]编号。如果在知道N的大小，我们可以从[1、N]中随机选择一个数作为选择对象。
但是现在不知道N的大小，要使每一个元素被取的概率相等（随机）。这个概念叫蓄水池抽样。
Solution：以1/i的概率取第i个元素。
证明：数学归纳法。
当i=1时：第1个元素以1/1=1的概率被取，符合条件。
设i=k时符合条件，即前k个元素都以1/k的概率被取。
则i=k+1时：对于第k+1个元素，被取概率为1/（k+1），符合条件。
对于前k个元素，每个元素被取的概率=被取并且没被第k+1个元素替换的概率=（1/k）*(1−1/（k+1）)=1/（k+1）符合条件。
综上所述：得证。
问题扩展：给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）？
同类：有l个奖品，一直有人来抽奖，一个奖品只能给一个人，最后才公布获奖，请设计一个算法使得每个人中奖的概率一样？
这次与上面唯一的不同是：总共需要取k个元素。仿照即可得出解决方案。
Solution：以1的概率取前k个元素，从i=k+1开始，以k/i的概率取第i个元素，若被取，以均等的概率替换先前被取的k个元素。
证明：同样数学归纳法。当i=k+1时：第k+1个元素以k/k+1概率被取，前k个元素被取的概率=1 - 被第k+1个元素替换的概率=1−k/(k+1)*1/k=k/(k+1) 符合条件。
设i=p时符合条件，即前p个元素都以k/p的概率被取。
则i=p+1时：对第p+1个元素，被取概率为k/(p+1)符合条件。
对于前p个元素，每个元素被取的概率=被取并且没有被第p+1个元素替换的概率=
k/p*((1−k/(p+1))+k/(p+1)*(1−1/k))=k/p+1同样符合条件。
综上所述：得证。
还有一种方法：给每个元素随机生成一个固定区间（如[0,1]）的权重。用一个大小为k的堆来选取权重较大的k个元素。仿照也可解决最开始的取1个的问题。
伪代码：《The Art of Computer Programming》
Init : a reservoir with the size： k
for i= k+1 to N
M=random(1, i);
if( M < k)
SWAP the Mth value and ith value
end for
Code
!/usr/bin/env python
#coding:utf-8
import random
import collections
#用蓄水池算法模拟从10个数中随机抽取一个数
def reservoir():
raw_list = [0,1,2,3,4,5,6,7,8,9]
ret_num = raw_list[0] #蓄水池初始化。因为只需要抽取一个，所以给一个变量即可
for i in range(1,10): #从第k+1个元素开始遍历
m = random.randint(1,i+1) #因为列表下标从0开始，所以随机数上限为i+1而不是i
if m <= 1:
ret_num = raw_list[i] #蓄水池里的元素替换
return ret_num
#抽取十万次，看看最后的结果
def run():
dic = collections.defaultdict(int)
for i in range(100000):
ret_num = reservoir()
dic[ret_num] += 1
for k,v in dic.items():
print k,":",v
run()