再帰アルゴリズムを使用して、セットのすべてのサブセットを系統的に見つけるにはどうすればよいでしょうか?

セットのサブセットの検索

セットのすべてのサブセットを決定することは、困難な作業となる場合があります。この問題に取り組むために再帰的アルゴリズムを利用するアプローチは次のとおりです。

n 個の要素を含むセットの場合、そのサブセットを 2 つのカテゴリに分けて考えることができます。n 番目の要素を含むものと含まないものです。

ステップ 1: 基本ケース

n が 1 の場合、サブセットは単純に次のようになります:

• {} (空のセット)
• {1}

ステップ 2: 再帰的ケース

集合 {1, ..., n-1 の部分集合がわかったら

• {1, ..., n-1} のサブセットのコピーを 2 つ作成します。
• 1 つのコピーの場合、各サブセットに n を追加します。
• 2 つのコピーの和集合を取得して、{1, ..., n} のサブセットを取得します。

例

集合 {1, 2, 3, 4, 5} について考えます。

• n = 1 の場合、サブセットは {{} , {1}}.
• n = 2 の場合、{}、{1} の各サブセットに 2 を加算します: {{2}, {1, 2}}。共用体を取得します: {{}、{1}、{2}、{1, 2}}。
• n = 3、4、および 5 についてプロセスを繰り返し、各要素をサブセットに追加します。前のステップ。

最後に、{1, 2, 3, 4, 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}}.

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