# Lexicographic Permutations – Algorithm L

The number of unique permutations with every N element being distinct is N!. However, what if there are repeating elements, but you still want the permutations to be unique? Well, then it could possibly be far less than N!.

For example, how many permutations are there of the following list of digits? 1,1,1,1,2,2,2,2. In this example N=8. It should be clear that there are not 8!=40320 possible unique permutations of these elements. The actual number of permutations is actually only 70.

The way to calculate that result is with this formula:

Lexicographic permutations with repeating elements = N! / (q1! * q2!*….qn!), where q1..qn represent the frequency that each element occurs. So in the example above the calculation is 8!/(4!*4!) q1=4 because there are 4 “1”s, and 4 “2”s.

This algorithm was called “Algorithm L” by Knuth in *The Art of Computer Programming*. The pseudo-code is below:

My Java implementation of this pseudocode is below: