0

例：1から10までの数字があります。すべての組み合わせで、すべての変数が繰り返されることなく1回含まれていますが、...まあ... 3628800（10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800）。

私の場合、コンピューターはランダムな組み合わせを選択するのではなく、すべての組み合わせをチェックする必要があります。あとは、システムは必要な組み合わせを配列に格納します。しかし、私はアルゴリズムを考えることができず、インターネットでアルゴリズムを見つけることができません（おそらく私が正しい方法を検索していないためです）。

すべての組み合わせに繰り返し変数がない場合、多数の変数を混合するためにどのアルゴリズムを使用できますか？

4

3 に答える 3

5

このために再帰的なアプローチを試すことができます。

アイデアは、どの番号が最初になるかを「推測」し、それを設定してから、配列の残りの部分を繰り返します。残りのすべての要素に対してこれらの「推測」を行うと、考えられるすべての順列が得られます。

これは、特定の配列のすべての順列を出力する一般的なケースのCコードです（配列内の繰り返し値を処理しません）。

void permute(int *array,int i,int length) { 
  if (length == i){
     printArray(array,length);
     return;
  }
  int j = i;
  for (j = i; j < length; j++) { 
     swap(array+i,array+j);
     permute(array,i+1,length);
     swap(array+i,array+j);
  }
  return;
}

このアプローチでは：配列に数値を事前入力します：1,2,...,n-そしてその上で順列アルゴリズムを呼び出します。

ideoneのとprint()関数swap()を含む簡単なテストケースでそれを見ることができます

于 2012-07-18T12:36:11.137 に答える
1

あなたが探しているのは順列と呼ばれています。

ウィキペディアにはいくつかの異なる方法がリストされています。

すべての順列を取得するための遅い方法

単純な遅い方法では、整数iを指定し、i番目の順列を返し、関数Nを呼び出す関数を作成します。回数。

ここでこの質問への答えを見てください。

インオーダーウェイ

辞書式順序は次のように記述されます。

次のアルゴリズムは、指定された順列の後に辞書式順序で次の順列を生成します。指定された順列をインプレースで変更します。

  1. a [k] <a [k+1]となる最大のインデックスkを見つけます。そのようなインデックスが存在しない場合、順列は最後の順列です。

  2. a [k]<a[l]となる最大のインデックスlを見つけます。k + 1はそのようなインデックスであるため、lは明確に定義され、k<lを満たします。

  3. a[k]をa[l]と交換します。

  4. a [k+1]から最後の要素a[n]までの順序を逆にします。

すべての順列を順番に取得するには、最初にシーケンスを並べ替える必要があります。

最小限の交換

速いかもしれませんが、クイックルックでコード例は見当たりませんでした。

Steinhaus-Johnson-Trotterアルゴリズムの説明を検討してください。

于 2012-07-19T00:58:14.607 に答える
0

整数のセットをシャッフルしようとしているようです：フィッシャー-イェーツシャッフル

于 2012-07-18T12:34:26.393 に答える