Using recursion to find all possible permutations of 2 arrays in Ruby-CodePudding

Pseudo-code.

# Suppose 2 arrays:
a1 = [a,b]
a2 = [x,y]

# Looking to find an array of all possible permutations across 2 elements
# Likely not phrasing this correctly, so here's the desired outcome
  a,x,b,x
  a,x,b,y
  a,y,b,x
  a,y,b,y
  b,x,a,x
  b,x,a,y
  b,y,a,x
  b,y,a,y

# Here's a visualization

      a
    /   \
  x       y
  |       |
  b       b
 / \     / \
x   y   x   y

yields solutions, reading from top tow
  a,x,b,x
  a,x,b,y
  a,y,b,x
  a,y,b,y

repeat with b on top for latter 4 solutions

# Trying to do the code recursively iterating through arrays

def test(a1,a2,outcome = [])
  a1.each do |e|
    if a2.size == 1
      return outcome << e,a2[0]
    else
      test(a2,a1.reject { |a| a == e }, outcome)
    end
  end
end

I have no idea how to get the desired outcome.

CodePudding user response：

What you are looking for is the product of each element of a1 with a2:

[:a] × a2
[:b] × a2

And then again the product of those two products.

We can express that in Ruby almost exactly like we express it in English:

x, y = a1.map {|el| [el].product(a2) }
(x.product(y)   y.product(x)).map(&:flatten)

This code not only solves your problem, it even solves the more general problem where a1 and a2 have an arbitrary number of elements.

CodePudding user response：

def moment_of_truth(a1, a2)
  (a1.permutation(2).to_a).product(a2.repeated_permutation(2).to_a).
    map { |(e1, e2), (f1, f2)| [e1, f1, e2, f2 ] }
end

moment_of_truth(['a', 'b'], ['x', 'y'])
  #=> [["a", "x", "b", "x"], ["a", "x", "b", "y"], ["a", "y", "b", "x"],
  #    ["a", "y", "b", "y"], ["b", "x", "a", "x"], ["b", "x", "a", "y"],
  #    ["b", "y", "a", "x"], ["b", "y", "a", "y"]]

moment_of_truth(['a', 'b'], ['x', 'y', 'z'])
  #=> [["a", "x", "b", "x"], ["a", "x", "b", "y"], ["a", "x", "b", "z"],
  #    ["a", "y", "b", "x"], ["a", "y", "b", "y"], ["a", "y", "b", "z"],
  #    ["a", "z", "b", "x"], ["a", "z", "b", "y"], ["a", "z", "b", "z"],
  #    ["b", "x", "a", "x"], ["b", "x", "a", "y"], ["b", "x", "a", "z"],
  #    ["b", "y", "a", "x"], ["b", "y", "a", "y"], ["b", "y", "a", "z"],
  #    ["b", "z", "a", "x"], ["b", "z", "a", "y"], ["b", "z", "a", "z"]]

moment_of_truth(['a', 'b', 'c'], ['x', 'y'])
  #=> [["a", "x", "b", "x"], ["a", "x", "b", "y"], ["a", "y", "b", "x"],
  #    ["a", "y", "b", "y"], ["a", "x", "c", "x"], ["a", "x", "c", "y"],
  #    ["a", "y", "c", "x"], ["a", "y", "c", "y"], ["b", "x", "a", "x"],
  #    ["b", "x", "a", "y"], ["b", "y", "a", "x"], ["b", "y", "a", "y"],
  #    ["b", "x", "c", "x"], ["b", "x", "c", "y"], ["b", "y", "c", "x"],
  #    ["b", "y", "c", "y"], ["c", "x", "a", "x"], ["c", "x", "a", "y"],
  #    ["c", "y", "a", "x"], ["c", "y", "a", "y"], ["c", "x", "b", "x"],
  #    ["c", "x", "b", "y"], ["c", "y", "b", "x"], ["c", "y", "b", "y"]]

moment_of_truth(['a', 'b', 'c'], ['x', 'y', 'z']) 
  #=> [["a", "x", "b", "x"], ["a", "x", "b", "y"], ["a", "x", "b", "z"],
  #    ["a", "y", "b", "x"], ["a", "y", "b", "y"], ["a", "y", "b", "z"],
  #    ["a", "z", "b", "x"], ["a", "z", "b", "y"], ["a", "z", "b", "z"],
  #    ["a", "x", "c", "x"], ["a", "x", "c", "y"], ["a", "x", "c", "z"],
  #    ["a", "y", "c", "x"], ["a", "y", "c", "y"], ["a", "y", "c", "z"],
  #    ["a", "z", "c", "x"], ["a", "z", "c", "y"], ["a", "z", "c", "z"],
  #    ["b", "x", "a", "x"], ["b", "x", "a", "y"], ["b", "x", "a", "z"],
  #    ["b", "y", "a", "x"], ["b", "y", "a", "y"], ["b", "y", "a", "z"],
  #    ["b", "z", "a", "x"], ["b", "z", "a", "y"], ["b", "z", "a", "z"],
  #    ["b", "x", "c", "x"], ["b", "x", "c", "y"], ["b", "x", "c", "z"],
  #    ["b", "y", "c", "x"], ["b", "y", "c", "y"], ["b", "y", "c", "z"],
  #    ["b", "z", "c", "x"], ["b", "z", "c", "y"], ["b", "z", "c", "z"],
  #    ["c", "x", "a", "x"], ["c", "x", "a", "y"], ["c", "x", "a", "z"],
  #    ["c", "y", "a", "x"], ["c", "y", "a", "y"], ["c", "y", "a", "z"],
  #    ["c", "z", "a", "x"], ["c", "z", "a", "y"], ["c", "z", "a", "z"],
  #    ["c", "x", "b", "x"], ["c", "x", "b", "y"], ["c", "x", "b", "z"],
  #    ["c", "y", "b", "x"], ["c", "y", "b", "y"], ["c", "y", "b", "z"],
  #    ["c", "z", "b", "x"], ["c", "z", "b", "y"], ["c", "z", "b", "z"]]

moment_of_truth(['a', 'b', 'c', 'd'], ['x', 'y', 'z', 'a']) # returns 192 arrays
  #=> [["a", "x", "b", "x"], ["a", "x", "b", "y"], ["a", "x", "b", "z"],
  #    ["a", "x", "b", "a"], ["a", "y", "b", "x"], ["a", "y", "b", "y"],
  #    ["a", "y", "b", "z"], ["a", "y", "b", "a"], ["a", "z", "b", "x"],
  #    ...
  #    ["d", "a", "c", "y"], ["d", "a", "c", "z"], ["d", "a", "c", "a"]]

See Array#permutation, Array#repeated_permutation and Array#product.

Note that because of the asymmetry between how a1 and a2 are treated, no guidance has been provided for how the addition of one more arrays (e.g., a1, a2 and a3) should be treated, so I have not addressed that case.

I don't see how recursion can be used here, but perhaps a reader can prove me wrong.