Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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|cite|improve this question
up vote 2 down vote accepted

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|cite|improve this answer
Thank you! You're right, this would be a cartesian product. – Dänu Feb 8 '12 at 9:45

Your Answer


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.