Permutations
There is a natural mapping between the integers 0, ..., n! − 1 (or equivalently the numbers with n digits in factorial representation) and permutations of n elements in lexicographical order, when the integers are expressed in factoradic form. This mapping has been termed the Lehmer code (or inversion table). For example, with n = 3, such a mapping is
| decimal | factorial | permutation |
| 010 | 000! | (0,1,2) |
| 110 | 010! | (0,2,1) |
| 210 | 100! | (1,0,2) |
| 310 | 110! | (1,2,0) |
| 410 | 200! | (2,0,1) |
| 510 | 210! | (2,1,0) |
The leftmost factoradic digit 0, 1, or 2 is chosen as the first permutation digit from the ordered list (0,1,2) and is removed from the list. Think of this new list as zero indexed and each successive digit dictates which of the remaining elements is to be chosen. If the second factoradic digit is "0" then the first element of the list is selected for the second permutation digit and is then removed from the list. Similarly if the second factoradic digit is "1", the second is selected and then removed. The final factoradic digit is always "0", and since the list now contains only one element it is selected as the last permutation digit.
The process may become clearer with a longer example. For example, here is how the digits in the factoradic 4041000! (equal to 298210) pick out the digits in (4,0,6,2,1,3,5), the 2982nd permutation of the numbers 0 through 6.
4041000! → (4,0,6,2,1,3,5) factoradic: 4 0 4 1 0 0 0! | | | | | | | (0,1,2,3,4,5,6) -> (0,1,2,3,5,6) -> (1,2,3,5,6) -> (1,2,3,5) -> (1,3,5) -> (3,5) -> (5) | | | | | | | permutation:(4, 0, 6, 2, 1, 3, 5)A natural index for the group direct product of two permutation groups is the concatenation of two factoradic numbers, with two subscript "!"s.
concatenated decimal factoradics permutation pair 010 000!000! ((0,1,2),(0,1,2)) 110 000!010! ((0,1,2),(0,2,1)) ... 510 000!210! ((0,1,2),(2,1,0)) 610 010!000! ((0,2,1),(0,1,2)) 710 010!010! ((0,2,1),(0,2,1)) ... 2210 110!200! ((1,2,0),(2,0,1)) ... 3410 210!200! ((2,1,0),(2,0,1)) 3510 210!210! ((2,1,0),(2,1,0))Read more about this topic: Factorial Number System
Famous quotes containing the word permutations:
“The new shopping malls make possible the synthesis of all consumer activities, not least of which are shopping, flirting with objects, idle wandering, and all the permutations of these.”
—Jean Baudrillard (b. 1929)
“Motherhood in all its guises and permutations is more art than science.”
—Melinda M. Marshall (20th century)