セット（ない冪）の全ての「ユニーク」サブセットを生成

Question

のは、我々はいくつかのサブセットが含まれている設定Sがあるとしましょう：a, b, c, d, eとf：

- [a,b,c] 
- [a,b] 
- [c] 
- [d,e,f] 
- [d,f] 
- [e] 

はのはまたSは、6つのユニークな要素が含まれていることを言ってみましょう。

Sの各固有の要素を含むSの可能なサブセットをすべて一度見つけることができますか？関数/メソッドの結果はそのような何かでなければなりません

：

1. [[a,b,c], [d,e,f]];
2. [[a,b,c], [d,f], [e]];
3. [[a,b], [c], [d,e,f]];
4. [[a,b], [c], [d,f], [e]].

は、任意のベストプラクティスや任意の標準がありますそれを達成する方法？

擬似コード、RubyまたはErlangの例に感謝します。

Answer 1

は、それはあなたが何であるかのように聞こえます探しているのは、セット/アレイのpartitionsです。

これを行う1つの方法は、再帰的である：

• 1個の素子アレイ[x]はxの形式X = [ヘッド] +尾部の配列は、その後であれば正確に一つのパーティション
• を有しますxのパーティションは、それぞれのパーティションをテールにして頭を追加することによって生成されます。たとえば、[3,2,1]のパーティションを生成し、[2,1]のパーティション[[2,1]]から[2,1]に3を追加するか、別の要素として追加するか[1,2,3]がある[5,3]の2つのパーティション[[3,2,1]または[2,1]、[3]]を与えます

ルビ実装は少し見えますhttps://github.com/sagivo/algorithms/blob/master/powerset.rb
：よう

def partitions(x) 
    if x.length == 1 
    [[x]] 
    else 
    head, tail = x[0], x[1, x.length-1] 
    partitions(tail).inject([]) do |result, tail_partition| 
     result + partitions_by_adding_element(tail_partition, head) 
    end 
    end 
end 

def partitions_by_adding_element(partition, element) 
    (0..partition.length).collect do |index_to_add_at| 
    new_partition = partition.dup 
    new_partition[index_to_add_at] = (new_partition[index_to_add_at] || []) + [element] 
    new_partition 
    end 
end 

Answer 2

なぜ貪欲アルゴリズムを使用しないのですか？

1）ソートSがサブセット長
2）私が聞かせて使用して降順設定：= 0
3）は、[i]は溶液
4）Sは、[J]ここで、j> iのような見つけるためにSを追加することあなたは、その後4で説明した要素
5.Aを見つけることができない場合）現在のソリューションに
5ない要素）を含んでいる透明な溶液
5.B）は、i>場合）は、i
5.C増加| S |その後、何の解決策が見つからない、壊れ;（ 5.D）後藤3

EDIT
うーん、もう一度あなたの記事を読んで、あなたがBest-First searchが必要という結論に来ます。あなたが必要とするものはChange-making problemとも呼ばれているので、あなたの質問は実際にはパーティションの問題ではありませんが、後者の状況では、最初の解決策が最良の解決策になります。実際にはすべての解決策を見つけたいので、 - 最初の検索戦略アプローチ。

Answer 3

古典的な "バックトラック"エクササイズのようです。

• ＃1：バックトラックで解決策が2回表示されないように、セットをeacotherに注文します。
• ＃2：current_set = []、set_list = []
• ＃3：ループset_listの最後のものよりも低い序列を持つすべてのセットを実行します（set_listが空の場合はすべて）。それをset_at_handとしましょう。
• ＃4：set_at_handにcurrent_setとの交差がない場合
• ＃4/true/1：それをcurrent_setに結合し、set_listにも追加します。
• ＃4/true/2：current_set complete？ true：set_listを正しい解のリストに追加します。current_setとset_listからset_at_handを削除
• ＃5：ループの終了
• ＃6：偽：＃3
• ＃4 /真/ 3に再帰的に返す

Answer 4

は、すべてのサブセット

def allSubsets set 
    combs=2**set.length 
    subsets=[] 
    for i in (0..combs) do 
     subset=[] 
     0.upto(set.length-1){|j| subset<<set[j] if i&(1<<j)!=0} 
     subsets<<subset 
    end 
    subsets 
end 

Answer 5

はここを見て生成しますこれは、配列のpowersetを見つけるために構築された単純なアルゴリズムです。