生成集合的所有“唯一”子集（不是powerset）

Let's say we have a Set S which contains a few subsets:

假设我们有一个包含几个子集的Set S:

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

Let's also say that S contains six unique elements: a, b, c, d, e and f.

我们还要说S包含六个独特的元素:a,b,c,d,e和f。

How can we find all possible subsets of S that contain each of the unique elements of S exactly once?

我们怎样才能找到包含S的每个独特元素的S的所有可能子集?

The result of the function/method should be something like that:

函数/方法的结果应该是这样的:

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

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

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

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

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

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

Is there any best practice or any standard way to achieve that?

是否有任何最佳实践或任何标准方法来实现这一目标?

I would be grateful for a Pseudo-code, Ruby or Erlang example.

我将非常感谢伪代码,Ruby或Erlang示例。

5 个解决方案

#1

It sounds like what you are looking for are the partitions of a set/array.

听起来你正在寻找的是一组/阵列的分区。

One way of doing this is recursively:

执行此操作的一种方法是递归:

a 1 element array [x] has exactly one partition

1个元素数组[x]只有一个分区

if x is an array of the form x = [head] + tail, then the partitions of x are generated by taking each partition of tail and adding head to each possible. For example if we were generating the partitions of [3,2,1] then from the partition [[2,1]] of [2,1] we can either add 3 to to [2,1] or as a separate element, which gives us 2 partitions [[3,2,1] or [[2,1], [3]] of the 5 that [1,2,3] has

如果x是x = [head] + tail形式的数组,那么x的分区是通过获取尾部的每个分区并为每个可能的头部添加头来生成的。例如,如果我们从[2,1]的分区[[2,1]]生成[3,2,1]的分区,我们可以将3添加到[2,1]或作为单独的元素,它为我们提供了[1,2,3]所拥有的5个分区[[3,2,1]或[[2,1],[3]]

A ruby implementation looks a little like

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

#2

Why not to use the greedy algorithm?

为什么不使用贪婪算法?

1) sort set S descending using the subsets length
2) let i := 0
3) add S[i] to solution
4) find S[j] where j > i such as it contains of elements which are not in current solution
5) if you can't find element described in 4 then
5.a) clear solution
5.b) increase i
5.c) if i > |S| then break, no solution found ;( 5.d) goto 3

1)排序集S使用子集长度下降2)令i:= 0 3)将S [i]添加到解4)找到S [j]其中j> i,例如它包含当前解不存在的元素5 )如果你找不到4中描述的元素那么5.a)明确解5.b)增加i 5.c)如果i> | S |然后休息,找不到解决方案;(5.d)转到3

EDIT
Hmm, read again your post and come to conclusion that you need a Best-First search. Your question is not actually a partition problem because what you need is also known as Change-making problem but in the latter situation the very first solution is taken as the best one - you actually want to find all solutions and that's the reason why you should you the best-first search strategy approach.

编辑嗯,再次阅读你的帖子,得出你需要Best-First搜索的结论。你的问题实际上不是一个分区的问题,因为你需要也被称为改变决策的问题,但在后一种情况下的第一个解决方案被视为最好的东西 - 你真的想找到所有的解决方案,这就是为什么你应该你是最好的搜索策略方法。

#3

It seems like a classic "backtrack" excercise.

这似乎是一个经典的“回溯”运动。

#1: Order your sets amongst eacother, so the backtrack will not give solutions twice.

#1:在eacother中订购你的套装,所以回溯不会给出解决方案两次。

#2: current_set = [], set_list=[]

#2:current_set = [],set_list = []

#3: Loop Run through all the set that have lower order mark than the last in the set_list, (or all if the set_list is empty). Let call it set_at_hand

#3:循环遍历所有具有低于set_list中的最后一个顺序标记的集合(或者如果set_list为空则为all)。我们称之为set_at_hand

#4: If set_at_hand has no intersection with current_set

#4:如果set_at_hand与current_set没有交集

#4/true/1: Union it to current_set, also add to set_list.

#4 / true / 1:将它连接到current_set,也添加到set_list。

#4/true/2: current_set complete? true: add set_list to the list of correct solutions. false: recurse to #3

#4 / true / 2:current_set完成? true:将set_list添加到正确解决方案列表中。 false:递归到#3

#4/true/3: remove set_at_hand from current_set and set_list

#4 / true / 3:从current_set和set_list中删除set_at_hand

#5: End of loop

#5:循环结束

#6: return

#4

generate all subsets

生成所有子集

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

#5

take a look here: https://github.com/sagivo/algorithms/blob/master/powerset.rb
this is a simple algorithm i built to find a powerset of an array.

看看这里:https://github.com/sagivo/algorithms/blob/master/powerset.rb这是我为查找数组的powerset而构建的一个简单算法。

#1