Cartesian product of n sets

I'm currently writing a little application in which I would like to create all permutations of n sets. For example I have the following sets (arrays):

s1 = { A, B, C }

s2 = { B, A }

s3 = { X, Y, Z }

...


What would be the most efficient way (algorithm) to get all the permutations?

With all permutations, I mean:

ABX, ABY, ABZ, AAX, AAY, AAZ, etc.


I already created a primitive algorithm using recursion, however I have no idea how to put this in maths and since I would like to optimize it and document it, I'd appreciate any help!

-

1 Answer

The appropriate term would be cartesian product, rather than permutations.

An algorithm for that would be to interpret each set as a set of digits, and the result as a number.

You can now enumerate through those in a manner similar to what happens with an odometer.

You keep increment the units digit first. When you hit the limit, you try incrementing the tens place (if not move left) and reset the units digit and continue in this manner till you reach the largest possible number.

This should give you an algorithm which would require very little space (as compared to a recursive solution), as you can compute the next result from the current one.

-
Thank you! You're right, this would be a cartesian product. –  Dänu Feb 8 '12 at 9:45