バックグラウンド
あなたが与えた式から-w！/ ((wn)! * n!) 問題セットは、異なる位置での重複を処理する順列ではなく、一意の組み合わせの数を計算する二項係数に関係しているようです。
あなたが言った：
「明らかに、ランダムなインデックスに到達するまで法的な順列を繰り返し計算してカウントする 3 番目のアプローチがありますが、それは単に最初のアプローチのスペースと時間のトレードオフであり、直接的には役に立ちません。これらの n 順列を数え上げる効率的な方法。
...
これは、乱数ソースが n! を区別するためにビットを生成することを余儀なくされたことを意味します。すべて同等の異なる結果。この余分なランダム性に頼らない効率的な方法があるかどうか知りたいです。おそらく、ビット位置の順序付けられていないリストを生成するアルゴリズムを使用するか、n 番目の一意のビット順列を直接計算することによります。」
そのため、k インデックスから n 番目の一意の組み合わせ、つまりランクを効率的に計算する方法があります。k-indexes は、一意の組み合わせを指します。たとえば、4 を選択 3 の n を k を選択するケースが採用されたとします。これは、n で表される合計 4 つの数 (0、1、2、3) を選択できることを意味し、それらは k で表される 3 つのグループで取得されます。一意の組み合わせの総数は n! として計算できます。/ ((k! * (nk)!) 0 のランクは、(2, 1, 0) の k-index に対応します。ランク 1 は、(3, 1, 0) の k-index グループによって表されます。など。
解決
k-index グループと対応するランクの間を反復せずに非常に効率的に変換するために使用できる式があります。同様に、ランクと対応する k-index グループの間を変換する式があります。
私はこの公式とパスカルの三角形からどのようにそれを見ることができるかについて論文を書きました。この論文は、Tablizing The Binomial Coeffieicentと呼ばれています。
論文で説明されている数式を実装するパブリック ドメインにある C# クラスを作成しました。メモリをほとんど使用せず、サイトからダウンロードできます。次のタスクを実行します。
任意の N choose K について、すべての k-index を適切な形式でファイルに出力します。K インデックスは、よりわかりやすい文字列または文字で置き換えることができます。
k-index を、ソートされた二項係数テーブル内のエントリの適切な辞書式インデックスまたはランクに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。パスカルの三角形に固有の数学的プロパティを使用してこれを行い、セット全体を反復する場合と比較して非常に効率的です。
ソートされた二項係数テーブルのインデックスを対応する k-index に変換します。使用される手法は、古い反復ソリューションよりもはるかに高速です。
Mark Dominusメソッドを使用して二項係数を計算します。これは、オーバーフローする可能性がはるかに低く、より大きな数で機能します。このバージョンは long 値を返します。int を返す他のメソッドが少なくとも 1 つあります。long 値を返すメソッドを使用していることを確認してください。
このクラスは .NET C# で記述されており、問題に関連するオブジェクト (存在する場合) をジェネリック リストを使用して管理する方法を提供します。このクラスのコンストラクターは、InitTable と呼ばれる bool 値を受け取ります。これが true の場合、管理対象のオブジェクトを保持する汎用リストが作成されます。この値が false の場合、テーブルは作成されません。上記の 4 つの方法を使用するためにテーブルを作成する必要はありません。テーブルにアクセスするためのアクセサ メソッドが用意されています。
クラスとそのメソッドの使用方法を示す関連するテスト クラスがあります。少なくとも 2 つのケースで広範囲にテストされており、既知のバグはありません。
次のテスト済みのコード例は、クラスの使用方法を示しており、一意の組み合わせごとに反復処理されます。
public void Test10Choose5()
{
String S;
int Loop;
int N = 10; // Total number of elements in the set.
int K = 5; // 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 indexes for a lexigraphic element.
int[] KIndexes = new int[K];
StringBuilder SB = new StringBuilder();
// 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(Combo, KIndexes);
// Verify that the Kindexes returned can be used to retrive the
// rank or lexigraphic order of the KIndexes in the table.
int Val = BC.GetIndex(true, KIndexes);
if (Val != Combo)
{
S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString();
Console.WriteLine(S);
}
SB.Remove(0, SB.Length);
for (Loop = 0; Loop < K; Loop++)
{
SB.Append(KIndexes[Loop].ToString());
if (Loop < K - 1)
SB.Append(" ");
}
S = "KIndexes = " + SB.ToString();
Console.WriteLine(S);
}
}
したがって、クラスを問題に適用する方法は、単語サイズの各ビットをアイテムの総数と見なすことです。これは、n!/((k! (n - k)!) 式の n になります。k、またはグループ サイズを取得するには、1 に設定されたビット数をカウントするだけです。リストまたは配列を作成する必要があります。この場合は 32 になります。クラスは N を処理しないことに注意してください N を選択、N を 0 を選択、または N を 1 を選択。 32 は 0 ケースを選択し、32 は 32 ケースを選択します. 32 が 1 を選択する場合は、32 を返す必要があります.
32 よりも大きくない値を使用する必要がある場合は、16 を選択します (32 アイテムの最悪のケース - 601,080,390 の一意の組み合わせが生成されます)。現在のクラスの実装方法である 32 ビット整数を使用できます。64 ビット整数を使用する必要がある場合は、64 ビット long を使用するようにクラスを変換する必要があります。long が保持できる最大値は 18,446,744,073,709,551,616 で、これは 2 ^ 64 です。 n が 64 のときに k を選択する場合の最悪のケースは、64 を選択して 32 を選択することです。 . それよりも大きな数値が必要な場合は、何らかの大きな整数クラスの使用を検討することをお勧めします。C# では、.NET フレームワークにBigInteger クラスがあります。別の言語で作業している場合、移植は難しくありません。
非常に優れた PRNG を探している場合、最速、軽量、高品質の出力の 1 つは Tiny Mersenne Twister または略して TinyMT です。コードを C++ と C# に移植しました。元の作成者の C コードへのリンクとともに、ここで見つけることができます。
Fisher-Yates のようなシャッフル アルゴリズムを使用する代わりに、次の例のようなことを検討することもできます。
// Get 7 random cards.
ulong Card;
ulong SevenCardHand = 0;
for (int CardLoop = 0; CardLoop < 7; CardLoop++)
{
do
{
// The card has a value of between 0 and 51. So, get a random value and
// left shift it into the proper bit position.
Card = (1UL << RandObj.Next(CardsInDeck));
} while ((SevenCardHand & Card) != 0);
SevenCardHand |= Card;
}
上記のコードは、52 枚ではなく 7 枚のカードでしか機能しないため、シャッフル アルゴリズムよりも高速です (少なくともランダム カードのサブセットを取得する場合)。また、カードを単一の 64 ビット ワード内の個々のビットにパックします。ポーカー ハンドの評価もより効率的になります。
余談ですが、非常に大きな数で機能することがわかった最高の二項係数計算機 (結果が 15,000 桁を超えるケースを正確に計算したもの) は、こちらで見つけることができます。