本文主要是介绍随机算法之蓄水池抽样问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
蓄水池抽样问题是从动态变化的N个元素中随机抽选出M个元素(N>=M)
算法描述如下：
Init : a reservoir with the size： kfor i= k+1 to NM=random(1, i);if( M < k)SWAP the Mth value and ith valueend for
由于N的个数是不确定的，这就意味着不论N的个数是多少，里面元素都要被等概率抽取,例如，先从10个元素中抽取2个出来，现在又往里面添加了10个元素，变成了从20个元素中抽取两个出来，如何保证这次变化后每个元素被抽取的概率还是一样的呢？
问题，证明对于任意样本号n,n>=k,每个样本作为取出样本的概率相等，即k/n
证明：
当n=k时，由我们把前k个数放入蓄水池可知，每个样本的取出概率均相等，即k/k=1。 设当前样本号为n，其每个取出样本概率均相等，即为k/n，我们要证明的是这种情况对于n+1也成立。
由于我们以k/(n+1)决定是否把n+1放入蓄水池，那么对于n+1其出现在蓄水池中的概率就是k/(n+1)，对于前n个元素中的任意元素m(k+1<=m<=n)，其出现在蓄水池中的概率为 m出现在蓄水池中的概率 * [(m+1被选中的概率*m没被m+1替换的概率 + m+1没被选中的概率)*(m+2被选中的概率*m没被m+2替换的概率 + m+2没被选中的概率)*…*(n+1被选中的概率*m没被n+1替换的概率 + n+1没被选中的概率)]
可见，对于n+1每个样本取出概率也相等，即为k/(n+1)。证毕。
面试题：
给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
此问题有个限制点：
1.元素个数不可知
2.只能遍历一边
解题思路如下：
1.遍历链表到第k个元素，构造一个数组A[K]存储这k个元素
2.从k+1开始遍历，与前面算法一样
for i= k+1 to N M=random(1, i);if( M < k)SWAP the Mth value and ith value in array A end for
3.最后得到的数组A[k]就是想要的。
在网上流传的这个算法有问题，wiki 上面的描述如下：
array R[k]; // result integer i, j; // fill the reservoir array for each i in 1 to k doR[i] := S[i] done; // replace elements with gradually decreasing probability for each i in k+1 to length(S) doj := random(1, i); // important: inclusive rangeif j <= k thenR[j] := S[i]fi done
（ps:注意第10行的 j <= k）
我个人倾向于有等号的算法，欢迎各位朋友讨论，指导。
参考链接：
http://hi.baidu.com/cpuramdisk/item/260611ca0082bcd796445239
http://en.wikipedia.org/wiki/Reservoir_sampling
这篇关于随机算法之蓄水池抽样问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
