如何創建一個數組的隨機排列？

我用C編寫了這個函數，我希望它創建一個隨機排列或從1到n的數字列表。我很難讓它沒有重複的數字。所以，如果你有N = 4，我想它返回一個包含各1-4只一次隨機排列，例如：{1,3,4,2}如何創建一個數組的隨機排列？

int* random(int n) 
{ 
    int* r = malloc(n * sizeof(int)); 
    // initial range of numbers 
    for(int i=0;i<n;++i){ 
     r[i]=i+1; 
    } 
    // shuffle 
    for (int i = 1; i <= n; ++i){ 
     int j = rand() % i; 
     r[i] = r[j]; 
     r[j] = i; 
    } 
    return r; 
}

來源

2013-04-12 user2238015

查找費希爾耶茨shuffle ... –

更改你的第二個for環路：

for (int i = n-1; i >= 0; --i){ 
    //generate a random number [0, n-1] 
    int j = rand() % (i+1); 

    //swap the last element with element at random index 
    int temp = r[i]; 
    r[i] = r[j]; 
    r[j] = temp; 
}

這是一個Fisher-Yates混洗算法。我聽說使用rand() % n不會統一分配，您已被警告。

如果您想要每次生成獨特的排列，您可以將生成的排列存儲在Dictionary或Hashmap中，然後在每次返回時查找。我不認爲C有一個內置的，但應該有可用的庫。

來源

2013-04-12 00:36:18 vidit

在像問題中的問題（更一般地說，有一個已知函數可以生成輸入序列）的情況下，一點時間可以是通過根本不生成原始非混洗序列來保存，如下所述：https：//en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm –

它可能不是最有效的方法，但由於您已經在開始填充數組，因此您可以循環遍歷元素併爲每個元素選擇一個範圍在1到n之間的隨機索引，並與該項目交換：

int* random(int n) 
{ 
    int* r = malloc(n * sizeof(int)); 
    for(int i=0;i<n;++i){ 
     r[i]=i+1; 
    } 
    for(int i=0; i<n; ++i){ 
     int randIdx = rand() % n; 
     // swap r[i] with r[randIdx] 
     int t = r[i]; 
     r[i] = r[randIdx]; 
     r[randIdx] = t; 
    } 
    return r; 
}

我不知道這是最有效的，或者即使它提供了最佳分配。但它很簡單:-)

來源

2013-04-12 00:37:04 Kirby

如何創建一個數組的隨機排列？

回答

相關問題