洗牌演算法：Fisher-Yates Shuffle 完整解析與 C++ 實作

前言

洗牌演算法是將有限序列隨機打亂的經典問題。**Fisher-Yates Shuffle（又稱 Knuth Shuffle）** 是唯一能產生均勻隨機排列、時間複雜度 O(n)、空間 O(1) 的原地演算法。本文詳細推導邏輯、提供 C++ 參考實作、分析常見錯誤變體與隨機數品質要求。

演算法核心邏輯

對長度為 n 的陣列 a[0..n-1]：

1. 初始化：a[i] = i（或任意初始順序）。
2. 從 i = n-1 遞減至 1：
3. 在 [0, i] 範圍均勻隨機選取索引 j。
4. 交換 a[i] 與 a[j]。

直觀理解：每一輪將「尚未確定位置的元素」中隨機挑一個放到當前尾端 i，確定其最終位置。

數學證明：均勻隨機性

• 第 n-1 位：從 n 個元素等概率 1/n 選出。
• 第 n-2 位：剩餘 n-1 個元素等概率 1/(n-1) 選出。
• ... 每個排列出現概率 = 1/n × 1/(n-1) × ... × 1/1 = 1/n!。

故所有 n! 種排列等概率，滿足嚴格均勻分佈。

C++ 參考實作（現代寫法）

#include 
#include 
#include 
#include 

// 通用版本：接受任意 RandomAccessIterator
template 
void fisher_yates_shuffle(RandomIt first, RandomIt last, URBG&& g) {
    for (auto i = last - 1; i > first; --i) {
        std::uniform_int_distribution dist(0, i - first);
        std::iter_swap(i, first + dist(g));
    }
}

// 便利封裝：使用標準隨機引擎
template 
void shuffle(RandomIt first, RandomIt last) {
    std::random_device rd;
    std::mt19937 gen(rd());
    fisher_yates_shuffle(first, last, gen);
}

int main() {
    const int N = 54; // 撲克牌 54 張
    std::vector cards(N);
    std::iota(cards.begin(), cards.end(), 0); // 0..53

    std::cout << "洗牌前: ";
    for (int c : cards) std::cout << c << ' ';
    std::cout << '\n';

    shuffle(cards.begin(), cards.end());

    std::cout << "洗牌後: ";
    for (int c : cards) std::cout << c << ' ';
    std::cout << '\n';
    return 0;
}

原文 C 風格實作分析

void shuffle(int boke[]) {
    int i, r, t;
    srand((unsigned)time(NULL));
    for (i = 1; i < 54; i++) {
        r = rand() % (54 - i) + i;          // 範圍 [i, 53]
        t = boke[i-1]; boke[i-1] = boke[r]; boke[r] = t;
    }
}

問題：

1. srand(time(NULL)) 若在同一秒內多次呼叫會產生相同序列。
2. rand() 通常為線性同餘法，統計品質差、週期短、低位隨機性弱。
3. rand() % N 產生模數偏差，除非 RAND_MAX+1 能被 N 整除。
4. 迴圈索引從 1 開始、交換 i-1 雖正確但不直觀。

修正建議： 改用 C++11 <random> 或 C 版 arc4random_uniform/random() 配合拒絕採樣消除模數偏差。

常見錯誤變體

隨機數品質要求

• 密碼學應用： 必須使用 CSPRNG（/dev/urandom、CryptGenRandom、std::random_device 直連硬體熵源）。
• 模擬/遊戲： std::mt19937（梅森旋轉）足夠，週期 2^19937-1，統計特性優異。
• 種子： 生產環境勿用 time(NULL)，應用 std::random_device 或系統熵池。

擴展：部分洗牌 / 流式洗牌

• 只需前 k 張： 僅跑前 k 輪迴圈，O(k) 時間。
• 資料流未知長度： Reservoir Sampling（水塘抽樣）可單遍歷均勻抽取 k 個元素。

總結

Fisher-Yates Shuffle 是洗牌問題的**標準答案**。現代 C++ 開發者應直接使用 std::shuffle（C++11）搭配 std::mt19937，避免手寫隨機邏輯引入偏差。理解其 O(n) 原地、均勻分佈的數學基礎，有助於在面試、系統設計、密碼學應用中做出正確選擇。