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

Question

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

7

假设我们有一个Set S，其中包含一些子集：

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

假设集合 S 包含六个唯一元素：a, b, c, d, e 和 f。我们如何找到包含每个唯一元素的 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 示例。

- skanatek

5个回答

1

为什么不使用贪心算法呢？

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

编辑
嗯，再次阅读您的帖子并得出结论，您需要最佳优先搜索。您的问题实际上不是一个分区问题，因为您需要的也被称为找零钱问题，但在后一种情况下，第一个解决方案被视为最佳解决方案-您实际上想要找到所有解决方案，这就是为什么您应该使用最佳优先搜索策略方法的原因。

- SOReader

0

请看这里：https://github.com/sagivo/algorithms/blob/master/powerset.rb
这是我编写的一个简单算法，用于查找数组的幂集。

- Sagiv Ofek

0

看起来像是一个经典的"回溯"练习。

#1：将你的集合彼此排序，这样回溯就不会给出重复的解。
#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完成吗？是：将set_list添加到正确解答列表。否：递归到#3
#4/true/3：从current_set和set_list中删除set_at_hand
#5：循环结束
#6：返回

- Notinlist

0

生成所有子集

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

- test30

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Frederick Cheung · Accepted Answer

看起来你需要的是一个集合/数组的分区(partitions)。其中一种递归方法如下：

只包含一个元素[x]的数组有且仅有一种分区
如果x是一个形如x=[head]+tail的数组，那么x的分区可以通过将tail的每个分区都加上head得到。例如，如果我们正在生成[3,2,1]的分区，则从[2,1]的分区中，我们可以将3添加到[2,1]中或作为单独的元素添加，这给出了[1,2,3]的5个分区中的2个分区[[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