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

Mary-Kate Olsen
リリース: 2024-11-13 15:46:02
オリジナル
947 人が閲覧しました

How can you systematically find all subsets of a set using a recursive algorithm?

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

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

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

ステップ 1: 基本ケース

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

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

ステップ 2: 再帰ケース

集合 {1, ..., n-1} のサブセットがわかったら、次のように構築できます。セット {1, ..., n} のサブセットを次のように作成します:

  • {1, ..., n-1} のサブセットのコピーを 2 つ作成します。
  • For 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 サイトの他の関連記事を参照してください。

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート