再帰アルゴリズムを使用してセットのすべてのサブセットを生成するにはどうすればよいでしょうか?

セットのすべてのサブセットの生成

指定されたセットのすべてのサブセットを決定する際、要素の数 (n) が重要な役割を果たします。 。効果的なアルゴリズムは、再帰的手法を利用してこれを実現します。

再帰的アルゴリズム

再帰的アルゴリズムは、要素ごとにサブセットを 2 つに分割できるという原理に基づいて動作します。カテゴリ: 要素を含むカテゴリとそれを除くカテゴリ。それ以外の場合、これら 2 つのパーティションは同一のサブセットを共有します。

n=1 から始まり、{} (空のセット) と {1} の 2 つのサブセットがあります。

n>1 については、次のことを決定します。 1,...,n-1 のサブセットを抽出し、それらを複製します。 1 つのセットには各サブセットに n が追加されますが、もう 1 つのセットは変更されません。これら 2 つのセットを結合すると、サブセットの完全なセットが得られます。

説明例

{1, 2, 3, 4, 5} のサブセットを生成してみましょう:

• n=1: {{} , {1}}
• n=2: Take {} , {1} 2 を追加します。 {} 、 {1} との結合: {{} 、 {1} 、 {2} 、 {1, 2}}
• n=3: 3 を追加します。 {{} 、 {1} 、 {2} 、 {1, 2} 、 {3} 、 {1, 3} 、 {2, 3} 、 {1, 2, 3}}
• n=4: 4 を追加: {{} 、 {1} 、 {2} 、 {1, 2} 、 {3} 、 {1, 3} 、 {2, 3} 、 {1, 2, 3}、{4}、{1, 4}、{2, 4}、{1, 2, 4}、{3, 4}、{1, 3, 4}、{2, 3, 4}、{ 1, 2, 3, 4}}
• n=5: 5 を加算します: {{} 、 {1} 、 {2} 、 {1, 2} 、 {3} 、 {1, 3} 、 {2, 3} 、 {1, 2, 3} 、 {4} 、 {1, 4} 、 {2, 4} 、 {1, 2, 4} 、 {3, 4} 、 {1, 3, 4} 、 {2, 3, 4} 、 {1, 2, 3, 4} 、 {5} 、 {1, 5} 、 {2, 5} 、 {1, 2, 5} 、 {3, 5} 、 {1, 3, 5} 、 {2, 3, 5} 、 {1, 2, 3, 5} 、 {4, 5} 、 {1, 4, 5} 、 {2, 4 、5}、{1、2、4、5}、{3、4、5}、{1、3、4、5}、{2、3、4、5}、{1、2、3、4 , 5}}

したがって、{1, 2, 3, 4, 5} の 32 個のサブセットすべてに到達します。

以上が再帰アルゴリズムを使用してセットのすべてのサブセットを生成するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。