如何在 Ruby 中递归查找二维数组的排列

Question

我有一个数组，其中的元素是不同大小的数组。例如：

[[3],[11,2],[11,2],[3]]

我想找到嵌套数组中所有单个项目的排列。对于上面的数组，我想要一个返回值：

[
  [3, 11, 11, 3],
  [3, 11, 2, 3],
  [3, 2, 11, 3],
  [3, 2, 2, 3]
]

我有一个可行的解决方案，但它似乎特别冗长：

array = [[3],[11,2],[11,2],[3]]
array.product(*array).map { |e| e.drop(1) }.uniq

我应该如何实现递归方法，以及它如何工作？我很难理解这个问题。

Answer 1

解决这个问题的传统方法是使用方法Array#product和Array#drop。

arr = [[3], [11,2], [11,2,7], [4]]

arr.first.product(*arr.drop(1))
  #=> [[3, 11, 11, 4], [3, 11, 2, 4], [3, 11, 7, 4],
  #    [3, 2, 11, 4], [3, 2, 2, 4], [3, 2, 7, 4]]

如果 的任何元素arr包含重复项，则返回值也将包含重复项。如果不需要重复项，请使用

arr.map(&:uniq).first.product(*arr.drop(1))

然而，提问者要求递归解决方案。可以写成如下：

def prod(arr)
  return arr if arr.size == 1
  t = prod(arr.drop(1))
  arr.first.flat_map { |x| t.map { |a| [x] + a } }
end

prod arr
  #=> [[3, 11, 11, 4], [3, 11, 2, 4], [3, 11, 7, 4],
  #    [3, 2, 11, 4], [3, 2, 2, 4], [3, 2, 7, 4]]