3

C＃では、さまざまなインデックスのリストを含むリスト配列を作成しました。異なるインデックスの2つの組み合わせの1つの組み合わせを表示したいと思います。1つの中の2つの組み合わせを繰り返さないでください。

ペアになっている14人のプレーヤーでテニストーナメントをコーディングしようとしています。各プレーヤーは、他のプレーヤーと2回ペアリングしてはなりません。

4

1 に答える 1

2

あなたの問題は、二項係数の領域に分類されます。二項係数は、合計 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. クラスとそのメソッドの使用方法を示す関連するテスト クラスがあります。2 つのケースで広範囲にテストされており、既知のバグはありません。

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

問題を解釈するには、2 つの異なる方法があります。テニスでは、トーナメントは通常、各試合の勝者が進むシングルエリミネーションを使用するように配置されています. ただし、一部のローカル クラブでは、各プレーヤーが他のプレーヤーと 1 回だけ対戦するラウンド ロビンも使用されています。これが問題のようです。

したがって、問題は、14 人のプレイヤー (N = 14) でプレイできる一意のマッチの総数を計算する方法です。各プレイヤーは他のプレイヤー 1 人だけと対戦します (つまり、K = 2)。二項係数の計算は次のとおりです。

ユニークな組み合わせの総数 = N! / (K! * (N - K)! )。！文字は階乗と呼ばれ、N * (N-1) * (N-2) ... * 1 を意味します。K が 2 の場合、二項係数は N * (N - 1) / 2 に減らされます。 、N に 14、K に 2 を代入すると、組み合わせの総数は 91 であることがわかります。

次のコードは、一意の組み合わせごとに反復します。

int N = 14;  // Total number of elements in the set.
int K = 2;  // Total number of elements in each group.
// 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);
// The Kindexes array specifies the 2 players, starting with index 0.
int[] KIndexes = new int[K];
// Loop thru all the combinations for this N choose K case.
for (int Combo = 0; Combo < NumCombos; Combo++)
{
   // Get the k-indexes for this combination.  
   BC.GetKIndexes(Loop, KIndexes);
   // KIndex[0] is the first player & Kindex[2] is the 2nd player.
   // Print out the indexes for both players.
   String S = "Player1 = Kindexes[0].ToString() + ", " +
      "Player2 = Kindexes[1].ToString();
   Console.WriteLine(S};
}

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

また、これはクラスのプロジェクトであるため、先生はより独創的な作品を探している可能性があるため、上記の回答を受け入れない可能性があることにも言及しておく必要があります. その場合は、ループの使用を検討することをお勧めします。解決策を提出する前に、彼に確認する必要があります。

于 2012-12-19T14:05:05.797 に答える