Skip to content

Lexicographic Permutations – Algorithm L

June 5, 2013

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:

Algorithm L Pseudocode

My Java implementation of this pseudocode is below:

Advertisements

From → Algorithms

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: