ruby - 生成集合的所有 "unique"子集(不是幂集)

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 = [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