CODEWITHSUNDEEP
rubyarrayscombinatorics
YoursTruly
YoursTruly

Reputation: 60

How do I create every combination of single elements selected from multiple arrays?

I have 5 arrays:

["A", "B", "C"]
["A", "B", "C", "D", "E"]
["A"]
["A", "B", "C", "D", "E", "F"]
["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"]

I would like to create a list of each combination as such:

["AAAAA","AAAAB","AAAAC", "AAAAD"...
 "BAAAA","BAAAB","BAAAC", "BAAAD"...]

Upvotes: 2

Views: 202

Answers (2)

Matt
Matt

Reputation: 20786

a = [
  ["A", "B", "C"],
  ["A", "B", "C", "D", "E"],
  ["A"],
  ["A", "B", "C", "D", "E", "F"],
  ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"]
]

a.inject(&:product).map(&:join)
# => ["AAAAA", "AAAAB", "AAAAC", ..., "CEAFM", "CEAFN", "CEAFO"]

Thanks to bluexuemei for the improved answer. The original solution was a.shift.product(*a).map(&:join).

A More Traditional Solution

With such a convenient library, these ruby one-liners seem almost like cheating.

Here is a more traditional way to solve this common problem that can be readily coded into other programming languages:

N = a.reduce(1) { |product,list| product * list.size } # 1350

combinations = []
0.upto(N-1) do |q|
  combo = []
  a.reverse.each do |list|
    q, r = q.divmod list.size
    combo << list[r]
  end
  combinations.push combo.reverse.join
end
combinations
# => ["AAAAA", "AAAAB", "AAAAC", ..., "CEAFM", "CEAFN", "CEAFO"]

The basic idea is to first calculate the total number of combinations N which is just the product of the length of all the lists. Each integer from 0 to N-1 then encodes all the information needed to provide unique indices into each list to produce each combination. One way to think of it is that the index variable q can be expressed as a 5-digit number, where each digit is in a different base, where the base is the size of the corresponding list. That is, the first digit is base-3, the second digit is base-5, the 3rd is base-1 (always 0), the 4th is base-6, and the 5th is base-15. To extract these values from q, this is just taking a series of repeated integer divisions and remainders, as done in the inner loop. Naturally this requires some homework, perhaps looking at simpler examples, to fully digest.

Upvotes: 14

bluexuemei
bluexuemei

Reputation: 419

a.reduce(&:product).map(&:join).size

Upvotes: 1

Related Questions