1

n 個の要素で構成される並べ替えられた配列Nがあるとします。ここで、kが与えられた場合、中間の組み合わせとなる k 組み合わせを生成するための非常に効率的な方法が必要です (すべてのk組み合わせが辞書順に並べ替えられている場合)。

例：

N = {a,b,c,d,e} , k = 3

1: a,b,c
2: a,b,d
3: a,b,e
4: a,c,d
5: a,c,e
6: a,d,e
7: b,c,d
8: b,c,e
9: b,d,e
10:c,d,e

組み合わせ番号 5 を生成するアルゴリズムが必要です。

組み合わせ数システムに関するウィキペディアのページでは、これを取得する方法が (貪欲な方法で) 説明されています。ただし、nは非常に大きく、nより小さいすべてのkの中間の組み合わせを見つける必要があるため、それよりもはるかに効率的なものが必要です。

関心の組み合わせは常に中間にあるので、それを見つけるための何らかの簡単な方法があることを願っています。たとえば、上記のリストの最初の k の組み合わせは常にNの最初のk 個の要素によって与えられ、同様に最後の組み合わせは常に最後のk 個の要素によって与えられます。中間の組み合わせも見つける方法はありますか？

http://en.wikipedia.org/wiki/Combinatorial_number_system

4

1 に答える 1

0

辞書編集インデックスまたは一意の組み合わせのランクから K インデックスを取得する方法を探している場合、問題は二項係数に該当します。二項係数は、合計 N 個の項目を持つ K 個のグループで一意の組み合わせを選択する問題を処理します。

二項係数を操作するための一般的な関数を処理するクラスを C# で作成しました。次のタスクを実行します。

  1. 任意の N choose K について、すべての K-index を適切な形式でファイルに出力します。K インデックスは、よりわかりやすい文字列または文字で置き換えることができます。

  2. K インデックスを適切な辞書式インデックスまたは並べ替えられた二項係数テーブル内のエントリのランクに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的プロパティを使用して行われ、セットの反復処理に比べて非常に効率的です。

  3. ソートされた二項係数テーブルのインデックスを対応する K インデックスに変換します。使用される手法は、古い反復ソリューションよりもはるかに高速です。

  4. Mark Dominusメソッドを使用して二項係数を計算します。これは、オーバーフローする可能性がはるかに低く、より大きな数で機能します。

  5. このクラスは .NET C# で記述されており、一般的なリストを使用して、問題に関連するオブジェクト (存在する場合) を管理する方法を提供します。このクラスのコンストラクターは、InitTable と呼ばれる bool 値を受け取ります。これが true の場合、管理対象のオブジェクトを保持する汎用リストが作成されます。この値が false の場合、テーブルは作成されません。上記の 4 つの方法を使用するためにテーブルを作成する必要はありません。テーブルにアクセスするためのアクセサ メソッドが用意されています。

  6. クラスとそのメソッドの使用方法を示す関連するテスト クラスがあります。いくつかのケースで広範囲にテストされており、既知のバグはありません。

このクラスについて読んでコードをダウンロードするには、二項係数の表化を参照してください。

次のテスト済みコードは、任意の N を選択 K の組み合わせについて辞書式要素の中央値を計算します。

void TestMedianMethod()
{
   // This test driver tests out the GetMedianNChooseK method.
   GetMedianNChooseK(5, 3);  // 5 choose 3 case.
   GetMedianNChooseK(10, 3); // 10 choose 3 case.
   GetMedianNChooseK(10, 5); // 10 choose 5 case.
}

  private void GetMedianNChooseK(int N, int K)
  {
     // This method calculates the median lexicographic index and the k-indexes for that index.
     String S;
     // Create the bin coeff object required to get all
     // the combos for this N choose K combination.
     BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
     int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
     // Calculate the median value, which in this case is the number of combos for this N
     // choose K case divided by 2.
     int MedianValue = NumCombos / 2;
     // The Kindexes array holds the indexes for the specified lexicographic element.
     int[] KIndexes = new int[K];
     // Get the k-indexes for this combination.  
     BC.GetKIndexes(MedianValue, KIndexes);
     StringBuilder SB = new StringBuilder();
     for (int Loop = 0; Loop < K; Loop++)
     {
        SB.Append(KIndexes[Loop].ToString());
        if (Loop < K - 1)
           SB.Append(" ");
     }
     // Print out the information.
     S = N.ToString() + " choose " + K.ToString() + " case:\n";
     S += "   Number of combos = " + NumCombos.ToString() + "\n";
     S += "   Median Value = " + MedianValue.ToString() + "\n";
     S += "   KIndexes = " + SB.ToString() + "\n\n";
     Console.WriteLine(S);
  }

出力：

5 choose 3 case:
   Number of combos = 10
   Median Value = 5
   KIndexes = 4 2 0


10 choose 3 case:
   Number of combos = 120
   Median Value = 60
   KIndexes = 8 3 1


10 choose 5 case:
   Number of combos = 252
   Median Value = 126
   KIndexes = 9 3 2 1 0

このクラスは、選択した言語にかなり簡単に移植できるはずです。目標を達成するために、クラスのジェネリック部分を移植する必要はおそらくないでしょう。使用する組み合わせの数によっては、4 バイト整数よりも大きなワード サイズを使用する必要がある場合があります。

于 2013-04-01T05:32:22.573 に答える