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.
Given an array-of-arrays like
[[5,6], , [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
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:
>> .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(, [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.product(*array_of_arrays[1...]) end puts easy_combinations([[5, 6], , [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], , [8, 9]].
Suppose we start with the right-most array,
[8, 9] which we break out into our two interim solutions:
We then move to the next array from the right, i.e.
, 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
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
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
class CombinationsTest < Minitest::Test def cases [ [[0,1],[2,3],[4,5]], [[1,2,3],,], [[0,1,2],[3,4],[5,6,7]] ] end def test_combinations cases.each do |test_case| assert combinations(test_case).sort == test_case.product(*test_case[1..]).sort end end end
I have published a short gist with this code and the associated unit test.
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
method and the second built the solutions iteratively using
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.
- A GitHub gist with the code discussed in the article
- Wikipedia entry for Outer product
There are no existing comments
Got your own view or feedback? Share it with us below …