生成集合的所有“唯一”子集（不是powerset）
假设我们有一个包含几个子集的Set S ：
- [a,b,c] - [a,b] - [c] - [d,e,f] - [d,f] - [e]
我们还要说S包含六个独特的元素： a, b, c, d, e和f 。
我们怎样才能找到包含S每个独特元素的S所有可能子集？
函数/方法的结果应该是这样的：
-
[[a,b,c], [d,e,f]]; -
[[a,b,c], [d,f], [e]]; -
[[a,b], [c], [d,e,f]]; -
[[a,b], [c], [d,f], [e]].
是否有任何最佳实践或任何标准方法来实现这一目标？
我将非常感谢伪代码，Ruby或Erlang示例。
听起来你正在寻找的是一组/arrays的分区 。
执行此操作的一种方法是递归：
- 1个元素数组[x]只有一个分区
- 如果x是x = [head] + tailforms的数组，那么x的分区是通过获取尾部的每个分区并为每个可能的头部添加头来生成的。 例如，如果我们从[2,1]的分区[[2,1]]生成[3,2,1]的分区，我们可以将3添加到[2,1]或作为单独的元素，它为我们提供了[1,2,3]所拥有的5个分区[[3,2,1]或[[2,1]，[3]]
ruby实现看起来有点像
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
为什么不使用贪婪算法？
1）排序集S使用子集长度下降
2）让i：= 0
3）将S [i]添加到溶液中
4）找到S [j]其中j> i，例如它包含当前解不存在的元素
5）如果你找不到4中描述的元素那么
5.a）明确的解决方案
5.b）增加我
5.c）如果我> | S | 然后rest，没有找到解决方案;（5.d）转到3
编辑
嗯，再读一遍你的post，得出你需要Best-First搜索的结论。 您的问题实际上不是分区问题，因为您所需要的也称为变更问题但在后一种情况下，第一个解决方案被视为最佳解决方案 – 您实际上想要找到所有解决方案，这就是您应该你是最好的搜索策略方法。
这似乎是一个经典的“回溯”运动。
- ＃1：在eacother中订购你的套装，所以回溯不会给出解决方案两次。
- ＃2：current_set = []，set_list = []
- ＃3：循环遍历所有具有低于set_list中的最后一个顺序标记的集合（或者如果set_list为空则为all）。 我们称之为set_at_hand
- ＃4：如果set_at_hand与current_set没有交集
- ＃4 / true / 1：将它连接到current_set，也添加到set_list。
- ＃4 / true / 2：current_set完成？ true：将set_list添加到正确解决方案列表中。 false：递归到＃3
- ＃4 / true / 3：从current_set和set_list中删除set_at_hand
- ＃5：循环结束
- ＃6：回归
生成所有子集
def allSubsets set combs=2**set.length subsets=[] for i in (0..combs) do subset=[] 0.upto(set.length-1){|j| subset<
看看这里： https ： //github.com/sagivo/algorithms/blob/master/powerset.rb
这是我为查找数组的powerset而构建的简单算法。