Given an array of size y, containing arrays of size n, how can I return all logical combinations using Ruby?

Question

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. It's important to note that only one item in each of the sub arrays can be in the results. (Such as "Completed Profile" can't also be in the results with "Not completed profile")

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!

Answer 1

While the answers provided were great and Jörg's is the one I accepted, I wanted to share the answer that one of my friends provided me in case anyone else encounters this question. Essentially it's Jörg's answer but with a bit more depth.

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

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"]]

Special thanks to Joel Quenneville of Thoughtbot for helping me with this as well as the rest of the people who provided answers.

Answer 2

By all means, use Array#product, but as in oft the case with Ruby, there are other ways. Here are two.

arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Use math to compute each of the arr.size**arr.first.size combinations

def cartesian_product(arr)
  n, m = arr.size, arr.first.size
  (0..n**m-1).map do |x|
    (n-1).downto(0).map do |i|
      x, r = x.divmod(m)
      arr[i][r]
    end.reverse
  end
end

cartesian_product arr
  #=> [[1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9],
  #    [1, 6, 7], [1, 6, 8], [1, 6, 9],
  #    [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9],
  #    [2, 6, 7], [2, 6, 8], [2, 6, 9],
  #    [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9],
  #    [3, 6, 7], [3, 6, 8], [3, 6, 9]]

Use recursion

def cartesian_product(arr)
  first, *rest = arr
  return first.map { |o| [o] } if rest.empty?
  c = cartesian_product(rest)
  first.flat_map { |o| c.map { |a| [o] + a } }
end

cartesian_product arr
  #=> same as above

In this application each element (array) of arr contains no duplicates. In other situations, where duplicates may be present (and where the products returned are not to contain duplicates), one should first compute

arr_without_dups = arr.map(&:uniq)

and then calculate the combinations from arr_without_dups.

Answer 3

It looks like you want to compute the cartesian product of the arrays. The method which computes the cartesian product is (not too surprisingly) called Array#product:

@task_states.first.product(*@task_states.drop(1))

So, for example:

['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"]]