蓄水池抽样

在高德纳的计算机程序设计艺术中，有如下问题：

可否在一未知大小的集合中，随机取出一元素？

例如在一很大，但未知确实行数的文字档中抽取任意一行。如果要确保每一行抽取的几率相等，即是说如果最后发现文字档共有N行，则每一行被抽取的几率均为1/N，则有如下算法（以Perl表示）

$line;
$n = 0;
srand;
while(<>) {
    $n++;
    $line = $_ if (rand < (1/$n));
}

以下Perl程序为上述程序之精简写法：

srand;
rand($.) < 1 && ($line = $_) while <>;

上例中，在循环内第n行被抽取的几率为1/n，以${\displaystyle P_{n}}$ 表示。如果文件共有N行，任意第n行被抽取的几率为

${\displaystyle {\begin{aligned}&P_{n}\prod _{k=n+1}^{N}(1-P_{k})\\=&{\frac {1}{n}}\prod _{k=n+1}^{N}(1-{\frac {1}{k}})\\=&{\frac {1}{n}}\prod _{k=n+1}^{N}{\frac {k-1}{k}}\\=&{\frac {1}{n}}{\frac {n}{n+1}}{\frac {n+1}{n+2}}\cdots {\frac {N-1}{N}}\\=&{\frac {1}{N}}\end{aligned}}}$ 

故此，各行被抽取的几率均相同。

由于上述算法不需要先把整个文件扫描以判定总行数再作抽样，此算法是一在线算法。

以上问题可扩展为

可否在一未知大小的集合中，随机取出k个元素？

亦即是说，如果文件共有${\displaystyle N\geq k}$ 行，则每一行被抽取的几率为${\displaystyle {\frac {k}{N}}}$ ，则算法为

$k = 輸出數量;
@lines;
$n = 0;
srand;
while(<>) {
    $n++;
    if ($n <= $k) {
        push(@lines, $_);
    } else {
        $r = int(rand($n));
        if ($r < $k) {
            $lines[$r] = $_;
        }
    }
}

上例中，在循环内第n行被抽取的几率为k/n，以${\displaystyle P_{n}}$ 表示。如果文件共有N行，任意第n行被抽取的几率为

${\displaystyle {\begin{aligned}&P_{n}\prod _{j=n+1}^{N}(1-{\frac {P_{j}}{k}})\\=&{\frac {k}{n}}\prod _{j=n+1}^{N}(1-{\frac {k}{kj}})\\=&{\frac {k}{n}}\prod _{j=n+1}^{N}{\frac {j-1}{j}}\\=&{\frac {k}{n}}{\frac {n}{n+1}}{\frac {n+1}{n+2}}\cdots {\frac {N-1}{N}}\\=&{\frac {k}{N}}\end{aligned}}}$ 

因此，各行被抽取的几率均相同。同理，此算法亦是在线算法。

在蓄水池算法的定义中，并没有要求每一项目被抽取的几率相同，然而相同几率的情况较常用。