10

この関数を C で作成しました。ランダムな順列または 1 から n までの数値のリストを作成したいと考えています。繰り返し番号を持たないようにするのに苦労しています。したがって、n = 4 の場合、1 ～ 4 をそれぞれ 1 回だけ含むランダムな配列を返したいと思います。たとえば、{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;
}
4

3 に答える 3

12

for2 番目のループを次のように変更します。

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() % nusingが均一に分散しないと聞いたことがありますが、警告されています。

また、毎回一意の順列を生成したい場合は、生成された順列をおそらくDictionaryまたはHashmapに保存し、戻るたびに検索できます。組み込みのものはないと思いますCが、利用可能なライブラリがあるはずです。

于 2013-04-12T00:36:18.877 に答える
0

これは最も効率的な方法ではないかもしれませんが、最初に配列にデータを入力しているので、要素をループして、要素ごとに 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-12T00:37:04.073 に答える