7

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

- [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 示例，我将不胜感激。

4

5 回答 5

3

听起来您正在寻找的是集合/数组的分区。

一种方法是递归：

  • 一个 1 元素数组 [x] 恰好有一个分区
  • 如果 x 是 x = [head] + tail 形式的数组，则 x 的分区是通过获取 tail 的每个分区并将 head 添加到每个可能的来生成的。例如，如果我们生成 [3,2,1] 的分区，那么从 [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
于 2011-12-27T11:31:28.610 回答
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

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

于 2011-12-27T11:01:32.850 回答
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 完成了吗？true：将 set_list 添加到正确解决方案列表中。false：递归到#3
  • #4/true/3: 从 current_set 和 set_list 中移除 set_at_hand
  • #5：循环结束
  • #6：返回
于 2011-12-27T11:04:30.307 回答
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
于 2012-03-08T17:07:00.050 回答
0

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

于 2015-04-30T19:16:59.907 回答