In Ruby, how can I iterate over an arbitrary number of arrays?

Question

I am doing something very much like the knapsack problem, in which I want to iterate over all combinations of an arbitrary number of inputs.

For example, if my function takes 3 arrays, I want to get all i×j×k combinations. If my function takes 5 arrays, I want to get all i×j×k×l×m combinations.

Example one:

result = all_products([1,2,3,4,5], [1,2,3], [10,20,30,40,50,60,70,80])

result.length == 120

Example two:

result = all_products([1,2,3], [1,2,3], [1,2,3], [1,2,3], [1,2,3], [1,2,3])

result.length == 729

But I don't know how many arrays I am going to take in.

What's the way to do this in Ruby?

This is NOT asking how to find all pairs of 1 array. My input arrays will likely all be different.

Here is what I tried so far:

def self.all_combinations(*sets)
 input = *sets; 
 prod = sets.inject(1) { |p,a| p * a.length } 
 prod.times do |p| 
  args = [] 
  index = p 
  input.each do |array| 
    quotient = index / array.length
    remainder = index % array.length
    args << array[remainder] 
    index = quotient
    pp args 
  end 
end

What have you tried so far? Can you give a small sample array and expected output? — whodini9, Mar 13 '17 at 19:59
Pass the args in with a splat operator for arbitrary number of args `all_products(*products)` This will assign them to `products` as an array of arrays. After that you should figure out how to cartesian product them. — Michael Papile, Mar 13 '17 at 20:11
@MichaelPapile, I know about splat. The question is how to iterate over the N arrays I will have at that point, not knowing how many arrays there will be when I write the function. — Dan Jameson, Mar 13 '17 at 20:13
Well, here's my attempt, using "pp" as my sample function. If you can't read it, ask the guy who locked this post. def self.all_combinations(*sets) input = *sets; prod = sets.inject(1) { |p,a| p * a.length } prod.times { |p| args = [] index = p input.each { |array| quotient = index / array.length remainder = index % array.length args << array[remainder] index = quotient } pp args } end — Dan Jameson, Mar 13 '17 at 20:23
This is a Cartesian product of arrays/sets. Once you have that splat put the arrays into an array it does not matter how many are entered. There are a ton of answers of this such as: http://stackoverflow.com/questions/2419370/how-can-i-compute-a-cartesian-product-iteratively Not in Ruby but it the logic is the same. You can do it iteratively or tail recursively. — Michael Papile, Mar 13 '17 at 20:24

score 1 · Answer 1 · answered Mar 14 '17 at 19:03

I would start off with getting the 'product' of 2 arrays:

def product2(array1, array2)
  array1.map { |e1| array2.map { |e2| e1*e2 } }.flatten
end

You can then generalize to any number of arrays:

def all_products(*arrays)
  arrays.reduce([1]) { |result, array| product2(result, array) }
end

You might want to handle corner cases (for example empty arrays or no input arrays at all)

In Ruby, how can I iterate over an arbitrary number of arrays?

1 Answers1