### 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]) # 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

- Ruby
`Array#product`

method - A GitHub gist with the code discussed in the article
- Wikipedia entry for Outer product
- Ruby
`Array#reduce`

method

## Comments

There are no existing comments

## Got your own view or feedback? Share it with us below …