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

Question

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.

Your question is confusing. In the title of your question, you are asking about combinations. In the code, you talk about permutations. However, permutations and combinations are different things, so which of the two is it? Also, your desired result looks neither like permutations nor like combinations, which just adds to the confusion. And the logic isn't clear either: if you are looking for "all possible" whatever-you-are-looking-for, and duplicating elements is allowed, as we can clearly see in the outputs a,x,b,x, a,y,b,y, b,x,a,x, and b,y,a,y, then where did a,x,a,x, … — Jörg W Mittag
– Jörg W Mittag, Commented Oct 27, 2021 at 20:09
… a,x,a,y, a,y,a,x, a,y,a,y, b,x,b,x, b,x,b,y, b,y,b,x, and b,y,b,y go? Never forget that computers are very, very dumb, and very, very literal, and they have no creativity, and don't take context into account; they also don't ask clarifying questions. If you cannot even write down what you want to achieve in a way that a human can understand it, then you will have no hope in explaining it to a computer! — Jörg W Mittag
– Jörg W Mittag, Commented Oct 27, 2021 at 20:11
That's essentially the product of each element of a1 with a2 and then again the resulting product of those two products: x, y = a1.map {|el| [el].product(a2)}; x.product(y). — Jörg W Mittag
– Jörg W Mittag, Commented Oct 27, 2021 at 20:32
a1 = [a,b] references two variables or methods whose values are not known: a and b. If you mean those to be literals you need to write something like a1 = ['a','b'] or a1 = [:a,:b]. At heart, it's an interesting question. — Cary Swoveland
– Cary Swoveland, Commented Oct 27, 2021 at 20:40

Jörg W Mittag · Accepted Answer · 2021-10-27 21:20:24Z

1

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.

edited Oct 27, 2021 at 21:20

answered Oct 27, 2021 at 20:43

Jörg W Mittag

371k79 gold badges457 silver badges666 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

james Over a year ago

yes thank you that semantically is better! question though, is there not a way to do this with a recursion that i was trying to start? i am working on an exercise in recursion and specifically trying to do it that way

Cary Swoveland Over a year ago

That solves the given problem, but does not generalize. For example, if a1 = ['a', 'b', 'c'] and a2 = ['x', 'y', 'z'], none of the elements of the array returned (each a 4-element array) begins with 'c': x, y = a1.map {|el| [el].product(a2) } (x.product(y) + y.product(x)).map(&:flatten).map(&:first).uniq #=> ["a", "b"].

Cary Swoveland · Accepted Answer · 2021-10-28 03:25:55Z

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.

Collectives™ on Stack Overflow

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

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related