ruby - 结合所有组合以获得完整的集合

Question

我有一个数组:

arr = [1, 2, 3]

我想找到所有的组合，然后组合这些组合，得到只包含一次arr所有元素的数组。顺序无关紧要。第一个组合应该返回类似的东西

combis = [
  [1], [2], [3],
  [1, 2], [1, 3], [2, 3], 
  [1, 2, 3]
]

我需要 valid，它具有 combis 的组合，其中包含来自 arr 的每个值恰好一次。所以:

valid = [
  [[1], [2], [3]],
  [[1], [2, 3]],
  [[2], [1, 3]],
  [[3], [1, 2]],
  [[1, 2, 3]]
]

这很快就会变大，所以我需要一种方法来执行此操作，而无需两次使用组合函数，然后过滤掉不正确的函数。

我觉得我需要使用某种树结构和递归来生成第二组组合，并在它不再是有效的最终集合时停止遍历。

如果有人可以帮助我编写(伪)代码，那就太好了。

Answer 1

使用Enumerator::Lazy立即拒绝不需要的/无效的组合:

combis = 1.upto(arr.size).each_with_object([]) do |i, acc|
  acc.concat arr.combination(i).to_a 
end 
#⇒ [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

valid = 1.upto(arr.size).each_with_object([]) do |i, acc|
  acc.concat(
    #                     ⇓⇓⇓⇓ THIS
    combis.combination(i).lazy.select do |e|
      items = e.flatten
      items.uniq.size == items.size && items | arr == items
    end.to_a
  )
end
#⇒ [[[1, 2, 3]], [[1], [2, 3]], [[2], [1, 3]], [[3], [1, 2]], [[1], [2], [3]]]