时间戳

首页 > 解决方案 > 组合所有组合以获得完整的集合

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

问题描述

我有一个数组：

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]]
]

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

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

如果有人可以帮助我使用（伪）代码，那就太好了。

标签： rubyalgorithm

解决方案

用于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]]]

推荐阅读