Enumerating Combinations with Ruby Arrays

Introduction

I recently undertook a ruby tech assessment under timed conditions … a humbling experience. Looking back on the car crash, one of the components where I sank waaay too much time was trying to enumerate the combinations that can be derived from an array-of-arrays.

This part of the challenge haunted me after the assessment, so to help process my trauma I decided to tackle the concept in this blog post. Come share in my journey.

The Problem

Given an array-of-arrays like [[5,6], [7], [8,9]], we need to return each distinct combination which can be built by taking one entry from each of the component arrays. So we will see that one acceptable combination would be [5, 7, 8], where we take the 5 from the first array, the 7 from the second array and the 8 from the third array. Another combination would be [5, 7, 9]. In fact, you may appreciate that, in this case all of our solutions will have the element 7 in the second slot, as this is the only option offered by the second array.

The full set of combinations are easily enumerated in this case; there are only four of them and they are:

    
[5, 7, 8]
[5, 7, 9]
[6, 7, 8]
[6, 7, 9]
    
  

The task was easy to complete in this small case, but we need a method to calculate all of these combinations regardless of the number of elements in the array, and regardless of the number of elements in each sub-array. You might already have a good idea of how you would achieve this, so perhaps you might want to have a go for yourself before reading any further …

… Back? OK, good. In this post I am going to present two options: an easy one and a not-so-easy one.

The Easy Solution

If you have a better knowledge of the Array API than I do, then you may be aware of an existing Array method that we can use to complete this task pretty easily, that being the Array#product method. Unfortunately, being unfamiliar with this method, I wasted mucho tiempo trying to do this by hand (unsuccessfully, may I add).

Eventually I had the wisdom to check the Array docs for tools that could help with the task and I stumbled across this beauty:

If you are mathematically inclined you might identify the similarity with the outer product in linear algebra. To get a feel for how this works, let's look at the output for a number of invocations:

    
>> [1].product([2,3])
=> [[1, 2], [1, 3]]
>> [1,2].product([3,4])
=> [[1, 3], [1, 4], [2, 3], [2, 4]]
>> [1,2].product([3,4], [5,6])
=> 
[[1, 3, 5],                              
 [1, 3, 6],                              
 [1, 4, 5],                              
 [1, 4, 6],                              
 [2, 3, 5],                              
 [2, 3, 6],                              
 [2, 4, 5],                              
 [2, 4, 6]]                              
>> [5,6].product([7], [8,9])
=> [[5, 7, 8], [5, 7, 9], [6, 7, 8], [6, 7, 9]]
    
  

The last example in the code sample is simply a recreation of the problem we evaluated in the introduction to this article. With this tool at our disposal we can fast-track a solution. We simply need to pull out the first array, and run this product method with each of the other arrays passed as arguments:

    
def easy_combinations(array_of_arrays)
  array_of_arrays[0].product(*array_of_arrays[1...])
end

puts easy_combinations([[5, 6], [7], [8, 9]]).inspect   # Returns  [[5, 7, 8], [5, 7, 9], [6, 7, 8], [6, 7, 9]]
    
  

The Not-So-Easy Solution

My frustration with the tech assessment was not that I took so long to eventually arrive at this solution with Array#product, but more because I had to give up on my home-rolled alternative. Let's see it through to the end now.

We will consider a step-by-step process for building our solutions. Again we will consider the simple example proposed in the introduction: [[5, 6], [7], [8, 9]]. Suppose we start with the right-most array, [8, 9] which we break out into our two interim solutions: [8] and [9]. We then move to the next array from the right, i.e. [7], we want to expand this into our existing interim solutions, giving [7, 8] and [7, 9]. We move to the left once more, i.e. [5, 6], and expand this into our existing solutions: [5, 7, 8], [5, 7, 9], [6, 7, 8] and [6, 7, 9]. I have tried to depict these two expansion steps, visually, below:

Using this pattern we will build our solutions with the following function:

    
def combinations(array_of_arrays)
  array_of_arrays.reverse.reduce([[]]) do |solutions, arr|
    cross_product(arr, solutions)
  end
end
    
  

This function will iterate through our array of arrays in reverse order and we will use reduce to accumulate our solutions. If you are unfamiilar with the Array#reduce method, it comes from the Enumerable module. It takes an initial value (in our case out empty solution set, [[]]) and it will iterate over the array executing a block for each element which yields this accumulated value along with the next item in the array. Within the block we call a yet-to-be-implemented method, cross_product, and we pass the sub-array which we are currently processing, along with our accumulated solutions. This cross_product method is responsible for carrying out the expansion steps illustrated in our diagram. Each element of arr must be expanded into the existing solution set to give our updated solution set, and the updated solution set should be returned. The implementation for the cross_product looks like this:

    
def cross_product(arr, array_of_arrays)
  products = []
  arr.each do |elem|
    array_of_arrays.map do |array|
      products.push(array.clone.unshift(elem))
    end
  end
  products
end
    
  

For sanity I chose not to mutate the entities passed into the cross_product method, so the variable products is introduced to store our updated solution set, and this is returned at the end of the method.

For each element in the array being processed, arr, we loop through the existing solutions, duplicate the solution and stuff the element into the front of the array. We then push this updated solution into the products array.

You can see how we have used reduce to iteratively build our solution set, expanding out by one array at a time. In each step we pass the updated solution set into the cross_product method to expand it futher, using the next sub-array. We can verify the output of our new home-rolled combinations generator against the values obtained from the easier Array#product approach:

    
class CombinationsTest < Minitest::Test

  def cases
    [
      [[0,1],[2,3],[4,5]],
      [[1,2,3],[5],[6]],
      [[0,1,2],[3,4],[5,6,7]]
    ]
  end

  def test_combinations
    cases.each do |test_case|
      assert combinations(test_case).sort == test_case[0].product(*test_case[1..]).sort
    end
  end
end
    
  

I have published a short gist with this code and the associated unit test.

Conclusion

As programmers we like to be creative with our solutions. Usually we should lean on what is already available, to avoid reinventing the wheel, but it is sometimes both informative and satisfying to work through an algorithm for ourselves.

In this post I have outlined two ways to enumerate the combinations that can be generated given an array-of-arrays. The first technique used the Array#product method and the second built the solutions iteratively using Array#reduce.

Thanks for reading. If you found this useful please consider subscribing so I can keep you up-to-date when I publish content in future.

References

1. Ruby Array#product method
2. A GitHub gist with the code discussed in the article
3. Wikipedia entry for Outer product
4. Ruby Array#reduce method