隨機抽獎演算法：從 N 個數中等概率抽取 M 個（水塘取樣）

需求

從 20 個數中抽 3 個，**每個數被選中的概率相等 (3/20 = 0.15)**，且**每輪必中 3 個**。

演算法：Reservoir Sampling (水塘取樣) Algorithm R

// 輸入：List items (size = n), int m (抽取數量)
// 輸出：List reservoir (size = m)
public static List reservoirSample(List items, int m) {
    List reservoir = new ArrayList<>(m);
    Random rand = new Random();
    for (int i = 0; i < items.size(); i++) {
        if (i < m) {
            reservoir.add(items.get(i)); // 前 m 個直接放入
        } else {
            int j = rand.nextInt(i + 1); // [0, i]
            if (j < m) {
                reservoir.set(j, items.get(i)); // 以 m/(i+1) 概率替換
            }
        }
    }
    return reservoir;
}

數學證明

• 第 i 個元素 (i ≥ m) 進入水塘的概率 = m / (i+1)。
• 進入後不被後續元素替換的概率 = ∏_{k=i+1}^{n-1} (1 - m/(k+1)) = (i+1-m)/(n-m)。
• 最終被選中概率 = m/(i+1) * (i+1-m)/(n-m) ... 經推導**所有元素最終概率均為 m/n**。

優勢

• **單次遍歷**，O(n) 時間，O(m) 空間。
• **不需知道總數 n**（可處理串流資料）。
• **無需排序/洗牌**，適合大數據/串流場景。

應用

每 20 個數作為一個批次，呼叫 reservoirSample(batch, 3) 即得 3 個等概率中獎號碼。