短い序文
組み合わせアルゴリズムは非常に頻繁に使用されます。 インターネットでは、組み合わせアルゴリズムに関する多くの情報を見つけることができます。 ただし、ロシア語のインターネットは、基本的に、サイクル内の組み合わせオブジェクトの連続的な列挙（生成）という最も単純なタスクを提供します。 例：
例
// 3 52 for (int i1 = 0; i1 < 50; ++i1) for (int i2 = i1+1; i2 < 51; ++i2) for (int i3 = i2+1; i3 < 52; ++i3) // ...
組み合わせ指数
各組み合わせ、順列、配置、およびその他の組み合わせオブジェクトをインデックスに関連付けることができます。これは、このアルゴリズムを反復するときに表示される番号です。
ここでは、より複雑な問題を検討します。その解決策はRunetで見つかりませんでした（ただし、1つのリンクを指定しますが、その式は明らかに間違っています）-組み合わせ自体（この場合、3つの数字のセット）に基づいてインデックスを見つけます。
ブルートフォースオプションがあります。 組み合わせカウンターをオンにし、上記のアルゴリズムを使用して、目的のオプションに到達するまで、すべてを順番に並べ替えます。 このオプションは時間的に非常に複雑なので、このオプションは破棄されます。
入力に番号i1、i2、i3があるとします。 まず、それらを昇順で配置する必要があります（上記の生成アルゴリズム自体は、常に順序付き形式で提供しますが、「組み合わせ」の概念は任意の順序を意味します）。
明確にするために、i1 = 3、i2 = 7、i3 = 12の順に並べてください。
これは、i1が0、1、2に等しいすべての組み合わせを「通過」したことを意味します。
i1 = 0の場合、インデックスi1、i2は51個の数字のうち2個のすべての組み合わせをカバーするため、C（2、51）の組み合わせを使用しました。
i1 = 1の場合、C（2、50）の組み合わせを使用しました。
i1 = 2の場合、C（2、49）の組み合わせを使用しました。
合計で、SUM {n = 0〜n = i1-1）C（2、51-n}を渡しました。
i1 = 3の場合、インデックスi2（およびi2 = i1 + 1 = 4で始まる）に沿って実行した組み合わせを既に検討します。
i2 = 4でC（1、47）の組み合わせが渡され、i2 = 5でC（1、46）の組み合わせが渡され、i2 = 6でC（1、45）の組み合わせが渡されました。
完全に類推すると、i2 = 7の場合、インデックスi3が実行された組み合わせを考慮します。
一般式を取得します：
希望する組み合わせインデックス= SUM {n = 0〜i1-1} C（2、51-n）+ SUM {n = i1 + 1〜i2-1} C（1、51-n）+ SUM {nから= i2 + 1 by i3-1} C（0、51-n）。
サブセットインデックス
組み合わせ論では、より複雑なオブジェクト、つまりサブセットへのパーティションもあります。 たとえば、52個の要素セットをそれぞれ2、3、47個の要素で構成される3つのサブセットに分割します。各サブセット内の要素の順序は重要ではありません。 （ちなみに、52個のうち2個の組み合わせは、それぞれ2個と50個の要素の2つのサブセットに分割する特殊なケースです）。
典型的な生成アルゴリズムは、52から2の組み合わせを生成し、ネストされたサイクルの各組み合わせに対して50から3の組み合わせを生成し、ネストされた組み合わせのインデックス（i3、i4、i5）がインデックスと一致しないことを確認することです（i1、i2）外部の組み合わせ：
C ++コード
// for (int i1 = 0; i1 < 51; ++i1) for (int i2 = i1+1; i2 < 52; ++i2) // for (int i3 = 0; i3 < 50; ++i3) if (i3 != i1 && i3 != i2) for (int i4 = i3+1; i4 < 51; ++i4) if (i4 != i1 && i4 != i2) for (int i5 = i4+1; i5 < 52; ++i5) if (i5 != i1 && i5 != i2) // ...
繰り返しますが、各パーティションには独自のインデックスがあります。
組み合わせインデックスを見つけるためのアルゴリズムを変更して、パーティションインデックスを見つけることができます。
インデックスを「外部の組み合わせ」i1、i2に配置し、インデックスi3、i4、i5を配置する必要があることに注意してください。ただし、最初の2つとは無関係です。
「ネストされた組み合わせ」では、基本的に50要素セットで作業していますが、インデックスi3、i4、i5は、0から51ではなく0から49に変化するように特定の方法で「シフト」する必要があります。
C ++コード
if (i3 >= i1) --i3; if (i3 >= i2) --i2; // i4, i5
（いわば、52個の要素セットからインデックスi1、i2を切り取り、残りのセットをシフトして穴を閉じますが、インデックスi3〜i5はシフトします）。
同時に、各「外部」の組み合わせの中に、正確にC（3、50）の「ネストされた」組み合わせがあることに注意する必要があります。
次に、アルゴリズムは次のようになります。
組み合わせインデックス（52のうちi1、i2）* NUMBERS_NUMBERS_OP_3_FOR_50 +組み合わせインデックス（インデックスシフト後の50のうちi3、i4、i5）。
一定の複雑さへのアルゴリズムの削減
たとえば、i1 = 0（n = 0〜-1の合計を検討）またはi2 = 1（1〜0の合計を検討）の場合、式には「エラー」があることに注意してください。 実際、そのような場合、対応する量はゼロに等しく取られるべきであり、結果は正しいでしょう。
また、アルゴリズムの時間的な複雑さにも注意を払う必要があります。Cを一定時間カウントする場合、線形の複雑さがあります。 これは、ブルートフォースよりも既に優れています。
しかし、実際には、ベースセットの固定ディメンション （この場合は52）については、アルゴリズムを一定の複雑さに減らすことを妨げるものはありません。 これを行うには、数学の知識を適用し、すべての量を分析的に計算します。
たとえば、組み合わせの数C（2、K）、式Kの形式で「明らかにする」場合！ /（（K-2）！* 2！）、2次の多項式に縮小されます。 そして、和の符号の下にあるので、自然系列の数のN次の和公式を適用し（ Wikipediaを参照）、3次の単一の多項式を取得できます。 明らかに、時間の複雑さは一定です。 （さらに、サブタイトルの冒頭で私が引用した「間違い」は、いかなる形でも現れず、公式は正しいままです）。
繰り返しますが、これはベースセットの固定寸法用です。 ただし、メタプログラミングを使用すると、コンパイラに「教える」ことでこの作業を実行できると確信しています。
2、3、47のパーティションインデックスのサンプルコード
int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) { // 2 52, C(3, 50) int offset = ( (52*51 - (51-i1)*(52-i1)) / 2 + (i2 - i1 - 1) ) * 19600; // "" , 0...49 if (i3 >= i1) --i3; if (i3 >= i2) --i3; if (i4 >= i1) --i4; if (i4 >= i2) --i4; if (i5 >= i1) --i5; if (i5 >= i2) --i5; // 3 // 0: // n = 0 i3-1 (2, 49-n) // = m = 50-i3 49 (m * (m-1) / 2) offset += (19600 - ( ((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3)) / 2 ) / 2 ); // 1: // n = i3+1 i4-1 (1, 49-n) offset += (((48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // n = i4+1 i5-1 (1) offset += (i5 - i4 - 1); return offset; }
あとがき
私のポーカーシミュレーター（テキサスホールデム）では、ハンドカード（2枚）とすべてのフロップカード（テーブルに3枚のカード）のすべての可能な組み合わせで勝つ確率を事前に計算して保存したかったのです。 これは、52セットの2、3、47のサブセットへのパーティションに対応します。
計算して保存しました。
しかし、特定の組み合わせのファイルからデータを読み取るときが来たとき、ギガバイトのファイルを長時間計算したり検索したりするのは本当に嫌でした。 ここで、ファイル内のオフセットを特定し、必要なものを直接読み取ります。
一般に、組み合わせアルゴリズムを次のクラスに分類します。
- 単一サイクルでの組み合わせオブジェクトの生成（すべてが単純で、例を挙げました）;
- 前のオブジェクト（C ++で表される一種の前方/後方反復子）を知っている次の（または前の）コンビナトリアルオブジェクトへの移行-ここでは、順列の一定時間の複雑さのアルゴリズムを提供するT. I. Fedoryaevaの研究ガイドに注目できますあなたはRuNetでそれを見つけることができますが、順列のためだけです-しかし、他の組み合わせオブジェクトの同様のアルゴリズムを見るのは面白いでしょう。
- オブジェクトのインデックスを見つける。 Fedoryaevaの許可、さらに線形の複雑さ、および再配置のみを除いて、例はまったくありません。
- インデックスによるオブジェクトの検索。
順列、組み合わせ、配置、サブセット、繰り返しのある組み合わせ、繰り返しのある配置など、すべての組み合わせオブジェクトの組み合わせアルゴリズムのガイドを入手するのは興味深いでしょう。