Combine array of array into all possible combinations, forward only, in Ruby

Question

I have an array of arrays, like so:

[['1','2'],['a','b'],['x','y']]

I need to combine those arrays into a string containing all possible combinations of all three sets, forward only. I have seen lots of examples of all possible combinations of the sets in any order, that is not what I want. For example, I do not want any of the elements in the first set to come after the second set, or any in the third set to come before the first, or second, and so on. So, for the above example, the output would be:

['1ax', '1ay', '1bx', '1by', '2ax', '2ay', '2bx', '2by']

The number of arrays, and length of each set is dynamic.

Does anybody know how to solve this in Ruby?

See also Creating permutations from a multi-dimensional array — aidan
– aidan, Commented Mar 31, 2016 at 6:41

Phrogz · Accepted Answer · 2012-04-10 19:37:57Z

62

Know your Array#product:

a = [['1','2'],['a','b'],['x','y']]
a.first.product(*a[1..-1]).map(&:join)

edited Apr 10, 2012 at 19:37

Phrogz

304k115 gold badges669 silver badges758 bronze badges

answered Mar 8, 2011 at 0:34

Andrew Grimm

82.3k58 gold badges210 silver badges355 bronze badges

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

5 Comments

Andrew Grimm Over a year ago

@Travis: If this answers your question, you can tick the tick/check mark next to the question.

bfontaine Over a year ago

It doesn't work for me : it gives me only ['1ax', '2by'] :/

Phrogz Over a year ago

@AndrewGrimm The answer using transpose did not do the right thing; I've edited your answer to remove it.

Phrogz Over a year ago

Also note that you can do: first, *rest = *a; combos = first.product(*rest).map(&:join); IMHO this extra line is a slight readability improvement over *a[1..-1].

jeffdill2 Over a year ago

Good lord, thank you for this answer. I've been breaking my brain for over a day trying to build out this functionality, having no idea that Ruby already had a method to accomplish exactly what I needed. :-/

Phrogz · Accepted Answer · 2011-03-08 00:35:33Z

Solved using a recursive, so-called "Dynamic Programming" approach:

For n-arrays, combine the entries of the first array with each result on the remaining (n-1) arrays
For a single array, the answer is just that array

In code:

def variations(a)
  first = a.first
  if a.length==1 then
    first
  else
    rest = variations(a[1..-1])
    first.map{ |x| rest.map{ |y| "#{x}#{y}" } }.flatten
  end
end

p variations([['1','2'],['a','b'],['x','y']])
#=> ["1ax", "1ay", "1bx", "1by", "2ax", "2ay", "2bx", "2by"]

puts variations([%w[a b],%w[M N],['-'],%w[x y z],%w[0 1 2]]).join(' ')
#=> aM-x0 aM-x1 aM-x2 aM-y0 aM-y1 aM-y2 aM-z0 aM-z1 aM-z2 aN-x0 aN-x1 aN-x2
#=> aN-y0 aN-y1 aN-y2 aN-z0 aN-z1 aN-z2 bM-x0 bM-x1 bM-x2 bM-y0 bM-y1 bM-y2
#=> bM-z0 bM-z1 bM-z2 bN-x0 bN-x1 bN-x2 bN-y0 bN-y1 bN-y2 bN-z0 bN-z1 bN-z2

You could also reverse the logic, and with care you should be able to implement this non-recursively. But the recursive answer is rather straightforward. :)

Sply Splyeff · Accepted Answer · 2015-03-21 17:28:33Z

6

Pure, reduce with product:

a = [['1','2'],['a','b'],['x','y']]
a.reduce() { |acc, n| acc.product(n).map(&:flatten) }.map(&:join)
#  => ["1ax", "1ay", "1bx", "1by", "2ax", "2ay", "2bx", "2by"]

answered Mar 21, 2015 at 17:28

Sply Splyeff

811 silver badge2 bronze badges

Collectives™ on Stack Overflow

Combine array of array into all possible combinations, forward only, in Ruby

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related