等概率無重複隨機抽題演算法（C 語言實作）

問題背景

題庫 n 道題，需抽取 m (m ≤ n) 道。簡單做法產生 m 個 [0, n-1] 隨機數，但：

1. 可能重複抽題。
2. 檢查重複並重抽，導致各題被抽中機率不均。

核心洞見：循環淘汰模型

將 1..n 視為圍成一圈的 n 人。每輪產生隨機數 round，從當前位置數到 round 號人退出，下輪從下一位繼續。此過程等價於：

• 已退出者編號「塌陷」：小於退出者編號不變，大於者遞減 1。
• 第 k 輪產生的隨機數 round_k，經過前 k-1 輪淘汰調整後，即為原始題庫中的真實索引。

高效演算法：插入排序法即時還原真實索引

維護一個已排序的已抽取索引陣列 intArray。第 i 輪：

1. 產生 temp = rand() % n。
2. 掃描 intArray[0..i-1]（已排序），對每個 intArray[j] ≤ temp，temp++（補償塌陷）。
3. 找到插入位置 k，將 intArray[k..i-1] 後移，temp 插入 k 處。
4. intArray[k] 即為本輪真實抽中題目索引。

完整 C 程式碼

int *intArray = malloc(m * sizeof(int));
int i, j, k, temp;
time_t t;
srand((unsigned)time(&t));

for (i = 0; i < m; i++) {
    temp = rand() % n;

    // 還原真實索引
    for (j = 0; j < i; j++) {
        if (temp >= intArray[j]) temp++;
        else { k = j; break; }
    }
    if (j == i) k = i;  // 插入尾部

    // 後移騰位並插入（維持陣列有序）
    for (j = i - 1; j >= k; j--)
        intArray[j + 1] = intArray[j];
    intArray[k] = temp;

    // 此處 intArray[k] 為本輪抽中題目索引（0-based）
    // 依題號生成試題...
}

// 保留原始抽取順序：額外陣列 intRandArray[m]
// intRandArray[i] = intArray[k] = temp;

free(intArray);

複雜度分析

• 時間：O(m²)（等價插入排序），m ≪ n 時極快。
• 空間：O(m)，無額外 O(n) 空間。
• 統計特性：無重複、等概率，每題被抽中機率嚴格等於 m/n。

隨機數品質提示

C 標準 rand() 品質有限。專業場景建議替換為：

• Mersenne Twister (MT19937)
• C++11 <random> 引擎（std::mt19937 + std::uniform_int_distribution）
• 作業系統密碼學級隨機源（/dev/urandom, CryptGenRandom）

將上述引擎整合至本演算法即得高品質抽題器。