配列のランダムな並べ替えを作成するには？

Question

私はこの関数を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; 
} 

Answer 1

はあなたに二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に1つが組み込まれているとは思わないが、利用できるライブラリがあるはずです。

Answer 2

これは最も効率的な方法ではないかもしれませんが、最初に配列に値を設定しているので、要素をループして、それぞれ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; 
} 

これが最も効率的かどうか、または最良の配布を提供しているかどうかわかりません。しかし、それはかなりシンプルです:-)