從1~N的整數中隨機選M個

01-28

這是一道常見的面試題，也是《The Art of Computer Programming vol.2》第 3.4.2 節的一道習題。

解決辦法很多，Fisher-Yates shuffle （需要 O(N) 空間）、Reservoir sampling （需要 O(N) 時間）都可行。Donald Knuth 在《Communications of ACM》 1986 年第 5 期給出了自己認為的最佳答案，見題圖。

基本思路是，用一個 sorted hash set，每次從 1~N 隨機選一個整數加入 set，直到 set 包含 M 個元素。Knuth 指出，當 M <= N/2 時，這個演算法的平均運行時間是 $O(M)$ ，需要的空間也是 $O(M)$ 。

我們來看看這個時間複雜度是怎麼算出來的。

根據幾何分布，如果每次試驗的成功率是 p，那麼平均要做 1/p 次試驗才能成功一次。舉例來說：

如果拋硬幣得正反面的概率都是0.5，一個人一直拋硬幣，直到拋出正面為止，那麼他平均要拋兩次才能得到一個正面。
如果生兒生女的概率都是0.5，一家人一直生娃，直到生出想要的性別為止，那麼平均要生兩個孩子才能有一個男孩（或女孩）。
如果擲骰子每一面的概率都是 1/6，那麼平均要擲 6 次才能得到想要的點數。同理，平均要擲 3 次才能得到 5 點或 6 點。

應用到我們這個題目這裡，

set 的第 1 個元素需要取 1 次隨機數
當 set.size() == 1 時，從 1~N 中隨機找出一個數，它已經位於 set 中的概率是 1/N，反之，它當 set 的第 2 個元素的成功概率是 (N-1)/N，因此平均要取 N/(N-1) 個隨機數才能讓 set.size() == 2
當 set.size() == 2 時，從 1~N 中隨機找出 set 的第 3 個元素的成功概率是 (N-2)/N，因此平均要取 N/(N-2) 個隨機數才能讓 set.size() == 3
依次類推，當 set.size() == M-1 時，從 1~N 中隨機找出 set 的第 M 個元素的成功概率是 (N-M+1)/N，因此平均要取 N/(N-M+1) 個隨機數才能讓 set.size() == M

因此，一共要取 N/N + N/(N-1) + N/(N-2) + ... + N/(N-M+1) = $N(H_N-H_{N-M})$ 次隨機數，通過將這個式子每項分母縮小為 N-M+1，可以證明它 < 2M。因此整個演算法平均是線性時間（在 M <= 1/2 N 的前提下）。 $H_n$ 的數值可以通過陳碩：用計算機計算1+1/2+1/3+...1/100000怎麼減少誤差？的方法計算。

Jon Bentley 認為這個問題可以用 O(M) 時間 O(1) 空間解決，怎麼做？

補充：對於 p=0.5 的情況，除了直接用幾何分布的均值，還可以用等差-等比數列求和來計算。例如 1/2 + 2/4 + 3/8 + 4/16 + ... + ${k}/{2^k}$ + ... = 2。