生成一组（而不是幂）的所有“独特的”子集

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。