C語言生成不重複隨機數組 - Fisher-Yates 洗牌算法實現

問題描述

需要生成一個包含 0 到 23 的隨機排列，即長度為 24 的數組，每個數字恰好出現一次，順序隨機。

常見誤區

• 反覆調用 rand() 並檢查重複：效率低，且當剩餘可用數字較少時極其緩慢。
• 在循環中反覆調用 srand(time(NULL))：若循環執行極快，種子相同導致生成相同序列。

正確做法：Fisher-Yates 洗牌算法

初始化數組 a[i] = i，然後從最後一個元素向前，每次隨機選擇一個未處理的位置交換。

代碼實現

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 24

void shuffle(int *arr, int n) {
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1); // 0 ~ i
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

int main() {
    srand((unsigned)time(NULL)); // 只調用一次！
    int a[N];
    for (int i = 0; i < N; i++) a[i] = i;
    shuffle(a, N);
    for (int i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

關鍵點解析

1. 只調用一次 srand()：通常在程序啟動時用當前時間作種子。
2. rand() % (i+1)：生成 0 到 i 的均勻隨機整數（雖有微小模數偏差，對 N=24 可忽略）。
3. 原地交換：空間複雜度 O(1)，時間複雜度 O(N)。
4. 均勻性：Fisher-Yates 算法保證所有 N! 個排列等概率出現。

進階：更好的隨機數源

若需高質量隨機（如密碼學），可使用 /dev/urandom (Linux) 或 CryptGenRandom (Windows)，或 C++11 的 std::mt19937。

總結

生成不重複隨機數組的標準解法是 Fisher-Yates 洗牌。避免在循環中重複播種，避免朴素去重法。上述代碼簡潔、高效、正確。