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

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

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.