algorithm - サブセットのリストからすべてのパーティションを検索します

Question

次のような特定のサブセットのリストが与えられます

S = [ {1, 2}, {3, 4}, {1}, {2, 3}, {4}, {3} ]

そして「宇宙」は次のように設定されます

U = {1, 2, 3, 4}

Sからのセットで作られたUのすべての可能なパーティションを見つけるために使用できるエレガントでシンプルなアルゴリズムは何ですか？この例では、そのようなパーティションには次のものが含まれます。

{1, 2} {3, 4}
{1, 2} {3} {4}

等

Answer 1

再帰を使用します。

最初の要素が使用されているかどうかに基づいて、問題を2つの小さな問題に分割します。

• {1,2}および残りのセットのいずれかを使用してパーティションを作成します。
• {1,2}残りのセットを使用せずにパーティション分割します。

これらの2つのオプションは、すべての可能性をカバーします。

• {3,4}1つ目は、。のみを使用してパーティション化することで解決され[ {3, 4}, {1}, {2, 3}, {4}, {3} ]ます。
• {1,2,3,4}2つ目は、。のみを使用してパーティション化することで解決され[ {3, 4}, {1}, {2, 3}, {4}, {3} ]ます。

これらの小さな問題を解決する方法については、この同様の質問を参照してください。