k-組み合わせを生成するアルゴリズム
1. 序章
このチュートリアルでは、要素を含むセットのすべての要素のサブセットを生成するためのさまざまなアルゴリズムについて学習します。 この問題は、-combinationsと呼ばれます。
組み合わせの数を見つけるための数学的解決策は簡単です。 二項係数と同じです。
たとえば、6つの要素を含むセットがあり、3つの要素のサブセットを生成するとします。 この場合、最初の要素を選択する方法は6つあります。 次に、残りの5つから2番目の要素を選択します。 最後に、残りの4つからサブセットの3番目で最後の要素を選択します。 これまでの選択肢の数は正確にです。
サブセットを作成しているので、選択の順序は重要ではないため、で割る必要があります。 したがって、同じ式に到達します。
ただし、そのようなサブセットをすべて生成して列挙することは、単にそれらを数えるよりも複雑です。 次のセクションでは、さまざまな方法でサブセットを作成するさまざまなアルゴリズムを見てみましょう。
次のセクションで確認するアルゴリズムは、最初に「TheArtofComputerProgramming」でコンピューター科学者のDonaldKnuthによってコンパイルされました。
2. 辞書式順序の生成
辞書式順序は、組み合わせを生成するための直感的で便利な方法です。
アルゴリズムは、要素を含むセットが存在することを前提としています：{0、1、…、}。 次に、最小の辞書式順序から始めて、形式の要素を含むサブセットを生成します。
アルゴリズムはすべての組み合わせにアクセスします。 これは、ネストされた複数のforループを再帰的に表します。 たとえば、= 3の場合、長さ3の組み合わせを生成するための3つのネストされたforループに相当します。
辞書式順序生成アルゴリズムの各反復で、増分できる最小値、つまり右端の要素を見つけます。 次に、後続の要素を最小値に設定します。
たとえば、=6および=3の場合、アルゴリズムは辞書式順序のシーケンスを生成します。
3. リュックサック世代を埋める
-combinationsをナップサック問題として定式化できます。 その後、最適なソリューションには、二項ツリー内のノードへのアクセスが含まれます。
3.1. 二項木
二項ツリーは、組み合わせ生成で使用されるツリーファミリーです。次のように、で示されます。
- = 0の場合、ツリーは単一のノードで構成されます
- の場合、順序の二項ツリーには、ルートと二項サブツリーが含まれます
たとえば、ルートとサブツリーが含まれています。
の別のコピーを挿入することで、それを繰り返し構築できることは簡単にわかります。 したがって、ノードが含まれます。 さらに、各レベルのノードの数は、{0、…、-1}のinに等しくなります。 この意味で、辞書式順序生成アルゴリズムのバリエーションは、レベルのノードをトラバースします。
3.2. リュックサックアルゴリズムの入力
0-1ナップサック問題を思い出してみましょう。ここでは、リュックサックを埋めるために一連のサイズから要素を取得するか、取得しないかのどちらかです。同様の方法で、問題を定式化できます。サイズのリュックサックがあり、集合Sの要素のすべてのサブセットの組み合わせを見つけたいと思います。を設定しましょう。 フォームに多数の要素があるサブセットは、この問題の有効な解決策です。
この場合、考えられるすべての解はのノードに対応します。 次のアルゴリズムを使用して、preorderの有効な各ノードにアクセスできます。
アルゴリズムは、の有効なノードのみを訪問し、無効なノードをスキップします。 初期化フェーズの後、のスペースを使い果たして、組み合わせにアクセスします。 次に、スペースの制限を超えずに、手元の組み合わせに要素を追加しようとします。 要素がリュックサックに収まる場合は、代わりに使用してすべての可能性を使い果たした後、それを配置します。
4. 回転ドアの生成
-combinationsの問題を表す別の方法は、グレイコードを使用することです。
4.1. グレイコード
2つの部屋をつなぐ回転ドアを想像してみてください。 左の部屋に人がいて、右の部屋に人がいます。 ですから、全部で人がいます。 この設定では、他の人と切り替えるだけで他の部屋に人を入れることができるため、部屋の人数は変わりません。
部屋の人々を表すために、ビットバイナリ文字列を使用します。 0は左の部屋の人を表し、1は他の部屋の人を表します。 したがって、2人が回転ドアを使用して場所を切り替えると、組み合わせ文字列ビットの2ビットが反転します。
繰り返さない組み合わせのシーケンスを生成するアルゴリズムを構築しましょう。
定義上、長さの灰色のバイナリコードを再帰的に生成します。 長さのバイナリコードを表します。 次のように、より正式に定式化できます。
つまり、長さ-1のグレイコードの先頭に0または1を挿入することにより、長さのグレイコードを生成します。
4.2. 回転ドアアルゴリズム
たとえば、=6と=3の場合を考えてみましょう。 生成しましょう：
ビット文字列を組み合わせに変換すると、明確なパターンが見られます。
このシーケンスでは、昇順で発生します。 ただし、の固定値の場合、は昇順で表示されます。 さらに、固定された組み合わせの場合、値は再び増加しています。 つまり、組み合わせの文字は交互に増減していると言えます。
すべてをまとめると、-combinationsにアクセスするための回転ドアアルゴリズムを構築します。
5. ほぼ完璧なスキームと完璧なスキーム
各ステップで1つだけが変更される場合、グレーパスシーケンスを同種と呼びます。複数のインデックスが同時に変更されるため、回転ドアアルゴリズムは同種シーケンスを生成しません。 たとえば、210から320または432から420への移行は、同質性の規則に従いません。
=6と=3の均質なグレイシーケンスを生成できます。
このビット文字列は、同種のシーケンスに対応します。
さらに良いことに、強く均質な遷移によってすべての組み合わせを生成できます。
Chaseは、ほぼ完全なシーケンスの計算が容易なバージョンを作成しました。 繰り返しますが、要素があり、-combinationsを見つけたいとしましょう。 したがって、1と0を含むバイナリシーケンスを再帰的に生成します。
その結果、このアルゴリズムを使用して、ほぼ完全な順序ですべての組み合わせにアクセスするシーケンスを生成できます。 それはチェイスのシーケンスと呼ばれます。 そのような組み合わせは正確に2つあります。
ほぼ完全な組み合わせから推測すると、隣接するビットを切り替えるだけで組み合わせシーケンスを生成できるのではないかと思います。 この形式は完全なスキームと呼ばれます。数学者は、またはまたはが奇妙な場合にのみ、完全な組み合わせを見つけることが可能であることを証明しました。 つまり、完璧なスキームを見つけることができるのは、4つのケースのうち1つだけです。
6. 比較
要約すると、-combinations生成問題はエレガントなパターンを構築します。 議論された戦略のバイナリ出力で構築されたヒートマップは、これらのパターンを追跡しやすくします。
上の画像は、「TheArt of ComputerProgramming」、第4A巻（2011）に掲載されました。
7. 結論
この記事では、集合の組み合わせを列挙する5つの異なる方法について学びました。 辞書式順序アルゴリズムは、名前が示すように、アルファベット順にサイズのサブセットを生成します。 回転ドアアルゴリズムは、辞書式順序を交互に繰り返す組み合わせを生成します。
同種世代は、連続する世代が1つの要素だけ異なることを保証します。 ほぼ完全なスキームは、変更された要素が最大2つのステップで移動することをさらに保証します。 完全なスキームでは、変更された要素のインデックスを1つだけインクリメントまたはデクリメントできます。
