生成一組（而不是冪）的所有「獨特的」子集

Question

比方說，我們有一組S其中包含幾個子集：

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

讓我們也說，S包含六個獨特的元素：a, b, c, d, e和f 。

我們如何才能找到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個元件陣列[X]具有正好一個分區
• 如果x是形式爲x = [頭] +尾，的陣列則x的分區是通過每個分區的尾部和每個可能的添加頭來生成的。例如，如果我們生成[3,2,1]的分區，然後從[2,1]的分區[[2,1]]中，我們可以將3添加到[2,1]或作爲單獨的元素，這給了我們[1,2,3]具有的2個分區[[3,2,1]或[[2,1]，[3]]具有

紅寶石實現看起來有點像

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）排序設置使用所述子集長度
2）讓I S降序：= 0
3）添加S [I]至溶液
4）求S [j]的其中j> i，使得它其不是在當前的解決方案
5個元素的含有）如果不能找到元件4中所述然後
5.A）澄清溶液
5.B）增加我
5.C）如果I> | S |再破，沒有找到解決辦法;（ 5.D）轉到3

編輯
嗯，再次讀您的文章，並走到那你需要一個Best-First search結論。你的問題實際上不是分區問題，因爲你需要的也被稱爲Change-making problem，但在後一種情況下，第一個解決方案被認爲是最好的解決方案 - 你實際上想要找到所有的解決方案，這就是爲什麼你應該最好的原因 - 第一種搜索策略方法。

Answer 3

這似乎是一個經典的「回溯」練習。

• ＃1：在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是否完整？ true：將set_list添加到正確解決方案的列表中。假：改乘＃3
• ＃4 /真/ 3：從current_set和set_list刪除set_at_hand
• ＃5：循環結束
• ＃6：返回

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

到這裏看看：https://github.com/sagivo/algorithms/blob/master/powerset.rb
這是一個簡單的算法，用於查找數組的powerset。