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

特定のセットのすべてのサブセットを決定するには、要素の数 (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: {} 、 {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 個のサブセットすべてに到達します。