蓄水池抽样问题（Reservoir Sampling）

问题描述：

1
2
3

从个元素中随机抽取个元素，但的个数无法事先确定。
在实际应用中，往往会遇到很大数据流的情况。因此，我们无法先保存整个数据流然后再从中选取，
而是期望有一种将数据流遍历一遍就得到所选取的元素，并且保证得到的元素是随机的算法。

抽样算法：

1.先选择n个元素中的前k个元素，保存在集合S中；

2.从第j(k+1 <= j <= n)开始，随机生成一个数 random = random % j + 1，random的取值范围为1~j。如果random <= k，则留下该元素，在S中随机选择一个元素进行替换；如果random > k，则放弃该元素。

3.重复2的步骤。

证明：
假定选择了k个元素
从k+1个元素开始，对于第k+1个元素，留下的概率，k/(k+1);对于S中的任意元素，留下的概率，

则对于任意第i个元素(k+1 <= i <= n)，对于第i个元素，留下的概率为k/i；对于S中的任意元素，留下的概率，