Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

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.

share|improve this answer
    
Thank you! You're right, this would be a cartesian product. –  Dänu Feb 8 '12 at 9:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.