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

再帰アルゴリズムを使用したセットのすべてのサブセットの検索

n 個の要素を含むセットが与えられた場合、考えられるすべてのサブセットを見つけるのは一般的なタスクです。この記事では、これを達成するための効率的な再帰アルゴリズムについて段階的に説明します。

再帰的アプローチ

このアルゴリズムは、各要素に対してセットには 2 つの可能性があります:

1. element: 要素を含む新しいサブセットが作成されます。
2. 要素を除外します: 要素を除外する新しいサブセットが作成されます。

各要素の両方の可能性を考慮することで、考えられるすべての組み合わせをカバーし、すべての組み合わせを見つけます。

段階的な説明

例として集合 {1, 2, 3, 4, 5} を見てみましょう。

1. 基本ケース: n=1 の場合、セットには単一の要素が含まれます(例: {1})。サブセットは、{{}} (空のセット) と {{1}} (1 だけを含む) です。

2. 再帰的ケース: n>1 の場合、分割できます。問題を 2 つの部分問題に分割します:

   • のサブセットを見つける{1, 2, 3, 4, 5-1}: 最初の n-1 要素のアルゴリズムを再帰的に呼び出し、サブセットのセットを取得します。
   • サブセット セット: 1 つのコピーはすべてのサブセットに要素 n を含めるためのもので、もう 1 つは要素 n を除外するためのものです。
   • インクルード コピーのサブセットに n を追加します。 たとえば、{{}、{1}、{2}} がある場合、5 を追加すると {{} になります。 、{1}、{2}、{5}、{1, 5}、{2, 5}}。
   • 2 つの結合を取得します。コピー: これにより、サブセットの完全なセットが得られます。

例

{1, のサブセットを計算してみましょう。 2、3、4、5}再帰的に:

• ステップ 1 (n=1): サブセット = {{}, {1}}
• ステップ 2 (n=2) ): サブセット = {{}, {1}, {2}, {1, 2}} (コピーを作成{2})
• ステップ 3 (n=3): サブセット = {{}、{1}、{2}、{1, 2}、{3}、{1 , 3}, {2, 3}, {1, 2, 3}} ({2} のコピーに 3 を追加します)
• ステップ4 (n=4): サブセット = {{}、{1}、{2}、{1, 2}、{3}、{1, 3}、{2, 3}、{1, 2 , 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}} ({3} に 4 を加えます) copy)
• ステップ 5 (n=5): サブセット = {{}、{1}、{2}、{1, 2}、{3}、{1, 3 }、{2, 3}、{1, 2, 3}、{4}、{1, 4}、{2, 4}、{1, 2, 4}、{5}、 {1, 5}, {2, 5}, {1, 2, 5}} ({4} コピーに 5 を追加します)

したがって、サブセットの完全なセットは {{} 、{1}、{2}、{1、2}、{3}、{1、3}、{2、3}、{1、2、3}、{4}、 {1, 4}、{2, 4}、{1, 2, 4}、{5}、{1, 5}、{2, 5}、{1, 2, 5}}。

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