池塘抽样法（水塘抽样）如何应用均等概率随机算法？

本文共计597个文字，预计阅读时间需要3分钟。

关联主题+链表随机节点+一般语言提供随机函数可实现数值的平均概率取值，但需考虑本主题的链表无法直接标记，若想直接使用下标，必然要花费空间存储数组。类推，如果...

关联题目 链表随机节点
一般语言提供了随机函数可以实现数的均等概率取，但是要考虑到本题目的链表无法直接标记，如果想直接使用下标,必然要花费空间存入数组。类推，如果是一个很大的文本流，无法在内存打开，那该如何是好？
于是，我们引入池塘抽样法（又称水塘抽样）

池塘抽样法

从S中抽取首k项放入「水塘」中
对于每一个S[j]项（j ≥ k）：
随机产生一个范围从0到j的整数r
若 r < k 则把水塘中的第r项换成S[j]项

用枚举数组S{1，2，3}来帮助理解：

1. 当遍历到S[1]时，概率为1，只有一个数那肯定不存在均等的概念
2. S[2]时，有两个数，那么使用随机函数(这里假定是rand，根据自己语言确定),rand(1)[表示在0-1随机取]，如果取到0则保留当前值S[2]，概率是1/2（rand（0））概率。如果取不到则保留原答案，由1.可知之前值只有S[1]，且概率为1，则此时取S[1]的概率为1 X 1/2。这是的S[1],S[2]的概率均等，都为1/2
3. S[3]时，有三个数，使用函数rand(2),取0时保留S[3]，概率为1/3。