时间戳

首页 > 解决方案 > 数组组合

arrays - 数组组合

问题描述

我正在使用 Ruby 2.7。

我有一个数组，它的元素是三样东西之一：字符串或整数，或者偶尔是另一个带有一对元素的数组（这次只有字符串或整数）。根据我的问题的定义，数组没有进一步的嵌套级别。

例子：

w = [1, 2, 'b', 4]
x = [[2, 'r'],[2, 'g']]
y = [[2, 'w']]
z = ['u', 6, [2, 'r']]

问题的上下文是内部数组表示在外部数组中使用的可选替代方案。我正在寻找所有可能的方法来从每个内部数组中选择一个元素（如果存在），并将该元素替换到外部数组中。

例子：

f(w) = [ [1, 2, 'b', 4] ]
f(x) = [ [2, 2], [2, 'g'], ['r', 2], ['r', 'g'] ]
f(y) = [ [2], ['w'] ]
f(z) = [ ['u', 6, 2], ['u', 6, 'r'] ]

每个选择（每个解决方案的内部数组）中的元素顺序无关紧要。输出中解决方案的顺序也无关紧要。

我可以强行选择/拒绝、转换和使用 Array#product; 但我正在寻找一种尽可能简洁和优雅的方法。

标签： arraysrubycartesian-product

解决方案

问题中给出的规则不精确且不完整，因此我已尽力推断它们是什么。

代码

def doit(arr)
  if arr.size == 1
    e = arr.first
    return e.is_a?(Array) ? (arr.map { |f| [f] }) : arr
  end
  (first, *rest), other = arr.partition { |e| e.is_a?(Array) }
  return [arr] if first.nil?
  prod = first.product(*rest)
  return prod if other.empty?
  prod.flat_map { |a| other.map { |e| [e, *a] } }
end

请参阅Enumerable#partition、Array#product和Enumerable#flat_map。

例子

doit [1, 2, 'b', 4]
  #=> [[1, 2, "b", 4]] 
doit [[2, 'r'],[2, 'g']]
  #=> [[2, 2], [2, "g"], ["r", 2], ["r", "g"]] 
doit [:a, [2, 'r'], :b, [2, 'g']]
  #=> [[:a, 2, 2], [:b, 2, 2], [:a, 2, "g"], [:b, 2, "g"],
  #    [:a, "r", 2], [:b, "r", 2], [:a, "r", "g"], [:b, "r", "g"]] 
doit [[2, 'w']]
  #=> [[[2, "w"]]] 
doit ['u', 6, [2, 'r']]
  #=> [["u", 2], [6, 2], ["u", "r"], [6, "r"]] 
doit [:a, [2, 3], :b, :c, [4, 5], :d, [6, 7]]
  #=> [[:a, 2, 4, 6], [:b, 2, 4, 6], [:c, 2, 4, 6], [:d, 2, 4, 6],
  #    [:a, 2, 4, 7], [:b, 2, 4, 7], [:c, 2, 4, 7], [:d, 2, 4, 7],
  #    [:a, 2, 5, 6], [:b, 2, 5, 6], [:c, 2, 5, 6], [:d, 2, 5, 6],
  #    [:a, 2, 5, 7], [:b, 2, 5, 7], [:c, 2, 5, 7], [:d, 2, 5, 7],
  #    [:a, 3, 4, 6], [:b, 3, 4, 6], [:c, 3, 4, 6], [:d, 3, 4, 6],
  #    [:a, 3, 4, 7], [:b, 3, 4, 7], [:c, 3, 4, 7], [:d, 3, 4, 7],
  #    [:a, 3, 5, 6], [:b, 3, 5, 6], [:c, 3, 5, 6], [:d, 3, 5, 6],
  #    [:a, 3, 5, 7], [:b, 3, 5, 7], [:c, 3, 5, 7], [:d, 3, 5, 7]]

请注意，返回值doit [[2, 'w']]与问题中给出的不同。

解释

步骤如下。

arr = [:a, [2, 'r'], :b, [2, 'g']]

(first, *rest), other = arr.partition { |e| e.is_a?(Array) }
  #=> [[[2, "r"], [2, "g"]], [:a, :b]]

Ruby 将数组分解应用于上述表达式以获得first,rest和的值other：

first
  #=> [2, "r"] 
rest
  #=> [[2, "g"]] 
other
  #=> [:a, :b]

继续，因为first.nil? #=> false在 中return [arr] if first.nil?，我们不返回。下一个：

prod = first.product(*rest)
  #=> [[2, 2], [2, "g"], ["r", 2], ["r", "g"]]

other.empty? #=> falsereturn prod if other.empty?所以我们不返回。

puts我可以通过在代码中插入语句并运行它来最好地解释剩余的计算。

prod.flat_map do |a|
  puts "a = #{a}"
  other.map do |e|
    puts "  e = :#{e}"
    puts "    [e, *a] = #{[e, *a]}"
    [e, *a]
  end
end
  #=> [[:a, 2, 2], [:b, 2, 2], [:a, 2, "g"], [:b, 2, "g"],
  #    [:a, "r", 2], [:b, "r", 2], [:a, "r", "g"], [:b, "r", "g"]]

显示以下内容。

a = [2, 2]
  e = :a
    [e, *a] = [:a, 2, 2]
  e = :b
    [e, *a] = [:b, 2, 2]
a = [2, "g"]
  e = :a
    [e, *a] = [:a, 2, "g"]
  e = :b
    [e, *a] = [:b, 2, "g"]
a = ["r", 2]
  e = :a
    [e, *a] = [:a, "r", 2]
  e = :b
    [e, *a] = [:b, "r", 2]
a = ["r", "g"]
  e = :a
    [e, *a] = [:a, "r", "g"]
  e = :b
    [e, *a] = [:b, "r", "g"]

推荐阅读