演算法逐步推導（一）：洗牌演算法 — 全域亂序 vs 費雪-耶茨優化版

問題背景

撲克牌 54 張，如何用 rand() 產生均勻隨機排列？介紹兩種演算法演進。

演算法一：全域洗牌法 (Naive Shuffle)

邏輯：對每個位置 i，從 全範圍 [0, 53] 隨機選一張交換。

void shuffle_naive(int *deck, int n) {
    for (int i = 0; i < n; i++) {
        int r = rand() % n;          // 0 ~ n-1
        int tmp = deck[i];
        deck[i] = deck[r];
        deck[r] = tmp;
    }
}

缺陷：機率分佈不均勻。總排列數 n!，但此演算法產生 n^n 種等概率路徑，n^n 無法整除 n! (n>2 時)，導致某些排列機率較高。且已洗好的牌會被再次交換，邏輯不直觀。

演算法二：費雪-耶茨洗牌法 / Knuth Shuffle (最佳解)

核心洞見：第 i 張牌只需從 剩餘未洗牌 [i, n-1] 中隨機選一張交換。已洗區段 [0, i-1] 確定不再動。

void shuffle_fisher_yates(int *deck, int n) {
    for (int i = 0; i < n; i++) {
        int r = i + rand() % (n - i);  // i ~ n-1
        int tmp = deck[i];
        deck[i] = deck[r];
        deck[r] = tmp;
    }
}

數學證明均勻性

• 第 0 張：從 n 張中等概率選 1 張 → 1/n
• 第 1 張：從剩餘 n-1 張中等概率選 1 張 → 1/(n-1)
• ...
• 任意排列機率 = 1/n × 1/(n-1) × ... × 1/1 = 1/n! ✓

關鍵細節與避坑

現代 C++ 標準庫一鍵調用

#include 
#include 

std::random_device rd;
std::mt19937 g(rd());
std::shuffle(deck, deck + n, g);  // 內部即 Fisher-Yates

教訓：直觀的「全域隨機交換」是錯的。演算法設計必須嚴謹證明機率分佈。Fisher-Yates 以 O(n) 時間、O(1) 空間、嚴格均勻，成為洗牌演算法的黃金標準。