Back to math.shaunlgs.com
Lehmer code is a way to identify every permutation of a string. Say we have a string "ABCDE", the permutations "ABCED", "ABDCE", "ABDEC",...etc can each be identified by lehmer code. This is useful because lehmer code is one-to-one with the permutation, it provides a way to list all the permutation without missing out any permutation.
Definition of lehmer code
What is lehmer code? Lehmer code is different from the normal numbering system we use. In normal number system, we start from 0
, and because the digit of the position is used up, to move on requires another position, so 10
, we say the radix of this numbering system is 10 because each position can only accomodate 10 digits i.e. 0 to 9.
Correct/ incorrect lehmer code
Lehmer code has radix that depends on its position index. Position index 0 has 0 radix, position index 1 has 1 radix, position index 2 has 2 radix... so the lehmer code 323
0 don't exist, but 321
0 does exist, because the position index 1 (the underlined position) can only has digit 0 or 1.
Lehmer code and integer
Lehmer code can be converted to integer, each position's value is the digit times the factorial of the position index, e.g. 32
10. The value of the position underlined is 2 * 2! = 4, the total value of the lehmer code is 3*3! + 2*2! + 1*1! + 0*0! = 23. The integer with its corresponding lehmer code is as follows:
Lehmer code and permutation
How does lehmer code match to permutation? What permutation of "ABCDE" match say 00210 (note: the length of lehmer code is the same as the string we want to permutate, in this case, 5)? Each lehmer digit means how many numbers to the right is originally on the left of the said permutation digit.
Lehmer code 00210 match string "ABCDE" to "ABEDC", referring to the permutated string, A has lehmer code 0, so no value to the right of A is originally on the left of A (B, E, D, and C are all originally on the right of A), check! B is the same. E has lehmer code 2, meaning there are 2 values to the right of E that are originally on the left of E, namely D and C, check!, D has lehmer code 1, meaning there is 1 value to the right of D that is originally on the left of D, namely C, check! C has lehmer code 0, this is because no number is to the right of C that is originally on the left of C.
Integer → Lehmer code → Permutation
The number of possible permutations for a given string is the factorial of its length, n!, for example, string "ABCDE" has length 5, so there are 5! = 120 possible permutations for the string. Since each integer has an unique lehmer code, and each lehmer code corresponds to a unique permutation, we can loop through the generation of lehmer code, then generation of permutation n! times.
Credit to Dr. Axel Rauschmayer