Algorithm to produce Cartesian product of arrays in depth-first order
- by Yuri Gadow
I'm looking for an example of how, in Ruby, a C like language, or pseudo code, to create the Cartesian product of a variable number of arrays of integers, each of differing length, and step through the results in a particular order:
So given, [1,2,3],[1,2,3],[1,2,3]:
[1, 1, 1]
[2, 1, 1]
[1, 2, 1]
[1, 1, 2]
[2, 2, 1]
[1, 2, 2]
[2, 1, 2]
[2, 2, 2]
[3, 1, 1]
[1, 3, 1]
etc.
Instead of the typical result I've seen (including the example I give below):
[1, 1, 1]
[2, 1, 1]
[3, 1, 1]
[1, 2, 1]
[2, 2, 1]
[3, 2, 1]
[1, 3, 1]
[2, 3, 1]
etc.
The problem with this example is that the third position isn't explored at all until all combinations of of the first two are tried. In the code that uses this, that means even though the right answer is generally (the much larger equivalent of) 1,1,2 it will examine a few million possibilities instead of just a few thousand before finding it.
I'm dealing with result sets of one million to hundreds of millions, so generating them and then sorting isn't doable here and would defeat the reason for ordering them in the first example, which is to find the correct answer sooner and so break out of the cartesian product generation earlier.
Just in case it helps clarify any of the above, here's how I do this now (this has correct results and right performance, but not the order I want, i.e., it creates results as in the second listing above):
def cartesian(a_of_a)
a_of_a_len = a_of_a.size
result = Array.new(a_of_a_len)
j, k, a2, a2_len = nil, nil, nil, nil
i = 0
while 1 do
j, k = i, 0
while k < a_of_a_len
a2 = a_of_a[k]
a2_len = a2.size
result[k] = a2[j % a2_len]
j /= a2_len
k += 1
end
return if j > 0
yield result
i += 1
end
end
UPDATE:
I didn't make it very clear that I'm after a solution where all the combinations of 1,2 are examined before 3 is added in, then all 3 and 1, then all 3, 2 and 1, then all 3,2. In other words, explore all earlier combinations "horizontally" before "vertically." The precise order in which those possibilities are explored, i.e., 1,1,2 or 2,1,1, doesn't matter, just that all 2 and 1 are explored before mixing in 3 and so on.
