A Ruby array problem that looks deceptively simple

Ruby
1

What I want to do is deal with n sets, while the code I provide below works with exactly 4 sets.

def show_combinations
  @combos = []
  ['A', 'no A'].each do |a|
    ['B', 'no B'].each do |b|
      ['C', 'no C'].each do |c|
        ['D', 'no D'].each do |d|
          @combos << [a, b, c, d]
        end
      end
    end
  end
end

How can I refactor this following code to deal with the following scenario:

Given I have an array of size y containing arrays of size n, I want to return all the combinations.

Background:

A user might have some tasks: for example, “Complete Profile” or “Set Up Email” or whatever. Those tasks can be represented like this:

@task_states = [["Completed Profile, NOT Completed Profile"], ["Set up Email", "NOT set up Email"]]

Then, passing @task_states into the method, the results should be this:

[
["Completed Profile", "Set up Email"],
["Completed Profile", "NOT set up Email"],
["NOT Completed Profile", "Set up Email"],
["NOT Completed Profile", "NOT Set up Email"]
]

So an array of arrays representing all the combinations. Obviously “Completed Profile” can’t also be in the same array as “NOT Completed Profile,” etc.

Thanks!

2

@superacidjax That’s a fascinating problem! Because you’re using nested eachs to build a flattened array, Array#flat_map immediately comes to mind. To get it to work for arbitrary sizes, I’m guessing you could combine that with Array#inject.

But… turns out Ruby already has you covered!

Cartesian products

What you are asking for is called the cartesian product and it’s already built in with Array#product.

For example:

[0, 1].product([0, 1])
# => [[0, 0], [0, 1], [1, 0], [1, 1]]

Notice that this gives us all possible 2-bit numbers, from 00-11 :slight_smile:

You can give Array#product any number of arrays:

[0, 1].product([0, 1], [0, 1])
# => [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

Notice that this gives us all the possible 3-bit numbers, from 000-111.

Your problem

Looking at your exact problem:

["A", "no A"].product(["B", "no B"], ["C", "no C"], ["D", "no D"])
=> [["A", "B", "C", "D"],
 ["A", "B", "C", "no D"],
 ["A", "B", "no C", "D"],
 ["A", "B", "no C", "no D"],
 ["A", "no B", "C", "D"],
 ["A", "no B", "C", "no D"],
 ["A", "no B", "no C", "D"],
 ["A", "no B", "no C", "no D"],
 ["no A", "B", "C", "D"],
 ["no A", "B", "C", "no D"],
 ["no A", "B", "no C", "D"],
 ["no A", "B", "no C", "no D"],
 ["no A", "no B", "C", "D"],
 ["no A", "no B", "C", "no D"],
 ["no A", "no B", "no C", "D"],
 ["no A", "no B", "no C", "no D"]]

gives you all the possible combinations from “ABCD” to “noA noB noC noD”

Generic solution

We can make this work with any generic array of arrays by leveraging the splat * operator.

def combinations(arrays)
  first, *rest = arrays
  first.product(*rest)
end

Then we can say:

arrays_to_combine = [["A", "no A"], ["B", "no B"], ["C", "no C"], ["D", "no D"]]
combinations(arrays_to_combine)
=> [["A", "B", "C", "D"],
 ["A", "B", "C", "no D"],
 ["A", "B", "no C", "D"],
 ["A", "B", "no C", "no D"],
 ["A", "no B", "C", "D"],
 ["A", "no B", "C", "no D"],
 ["A", "no B", "no C", "D"],
 ["A", "no B", "no C", "no D"],
 ["no A", "B", "C", "D"],
 ["no A", "B", "C", "no D"],
 ["no A", "B", "no C", "D"],
 ["no A", "B", "no C", "no D"],
 ["no A", "no B", "C", "D"],
 ["no A", "no B", "C", "no D"],
 ["no A", "no B", "no C", "D"],
 ["no A", "no B", "no C", "no D"]]
3

Wow! Thanks for this response. I’m just going through it and will test it out in the morning.

4

Just FYI Joel, I had originally posted this question on StackOverflow and got some similar answers, but your explanation was by far the best. So I posted your answer here: Given an array of size y, containing arrays of size n, how can I return all logical combinations using Ruby? - Stack Overflow

Providing you with credit of course and a link to Upcase just to ensure that credit is given where it is due!

Thanks so much. This answer helped unblock me!