再帰的アプローチを使用してセットのすべてのサブセットを見つけるにはどうすればよいでしょうか?

セットのすべてのサブセットの検索

n 個の要素のセットが与えられた場合、サブセットはそれらの要素の任意の組み合わせです。目標は、考えられるすべてのサブセットを生成する包括的なアルゴリズムを見つけることです。

再帰的解決策

次のアルゴリズムを考えてみましょう:

• 基本ケース: セットに要素が 1 つしか含まれていない場合、アルゴリズムは空のセットとその要素を含むセットを返します。
• 再帰ステップ: n 個の要素を含むセットの場合、最初の n-1 個の要素のサブセットのセットを見つけます。
• 分割: 前のセットを 2 つのグループに分割します。 n 番目の要素とそうでないサブセット。
• Union: これら 2 つのグループの和集合を取得して、完全なセットを形成します。

例: {1,2,3,4,5}

ステップ 1: {1,2,3, のすべてのサブセットを検索します。 4}。これらは次のとおりです: {}、{1}、{2}、{3}、{4}、{1,2}、{1,3}、{1,4}、{2,3}、{2,4 }、{3,4}、{1,2,3}、{1,2,4}、{1,3,4}、{2,3,4}、および {1,2,3,4} .

ステップ 2:ステップ 1 の各サブセットに 5 を加算し、サブセットと結合します。

• {} -> {}
• {1} -> {1} と {1,5}
• {2} -> {2} と {2,5}
• ...
• {1,2,3,4} -> {1,2,3,4} と {1,2,3,4,5}

これらのサブセットを結合すると、{1,2,3, 4,5}:

{ {}、{1}、{2}、{3}、{4}、{5}、{1,2}、{1,3}、 {1,4}、{1,5}、{2,3}、{2,4}、{2,5}、{3,4}、{3,5}、{4,5}、{1 ,2,3}、{1,2,4}、{1,2,5}、{1,3,4}、{1,3,5}、{1,4,5}、{2,3 ,4}、{2,3,5}、 {2,4,5}、{3,4,5}、{1,2,3,4}、{1,2,3,5}、{1,2,4,5}、{1,3 ,4,5}、{2,3,4,5}、および {1,2,3,4,5} }

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