Factoradic

In combinatorics, factoradic is a specially constructed number system. Factoradics provide a lexicographical index for permutations, so they have potential application to computer security. The idea of the factoradic is closely linked to that of the Lehmer code. An article by James D. McCaffrey documents the factoradic index for permutations with supporting code written in C#, acknowledging Peter Cameron as having made the original suggestion. The origins of the term 'factoradic' are obscure.

Definition

Factoradic is a factorial-based mixed radix numeral system: the "i"-th digit, counting from right, is to be multiplied by "i"!

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 which 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 howthe digits in the factoradic 4₆0₅4₄1₃0₂0₁0₀ (equal to 2982₁₀) pick out the digits in the 2982nd permutation of (0,1,2,3,4,5,6) — (4,0,6,2,1,3,5). 4₆0₅4₄1₃0₂0₁0₀ → (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)

Of course the natural index for the group direct product of two
permutation groups is just the factoradics for the two groups joinedusing concatenation. concatenated decimal factoradics permutation pair 0₁₀ 0₂0₁0₀0₂0₁0₀ ((0,1,2),(0,1,2)) 1₁₀ 0₂0₁0₀0₂1₁0₀ ((0,1,2),(0,2,1)) ... 5₁₀ 0₂0₁0₀2₂1₁0₀ ((0,1,2),(2,1,0)) 6₁₀ 0₂1₁0₀0₂0₁0₀ ((0,2,1),(0,1,2)) 7₁₀ 0₂1₁0₀0₂1₁0₀ ((0,2,1),(0,2,1)) ... 22₁₀ 1₂1₁0₀2₂0₁0₀ ((1,2,0),(2,0,1)) ... 34₁₀ 2₂1₁0₀2₂0₁0₀ ((2,1,0),(2,0,1)) 35₁₀ 2₂1₁0₀2₂1₁0₀ ((2,1,0),(2,1,0))

References

* Donald Knuth. "The Art of Computer Programming", Volume 2: "Seminumerical Algorithms", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Pages 65–66.
* James McCaffrey, [http://msdn2.microsoft.com/en-us/library/aa302371.aspx "Using Permutations in .NET for Improved Systems Security"] , MSDN.

ee also

* Combinadic
* Factorial

External links

* [http://www.numdam.org/item?id=BSMF_1888__16__176_0 Laisant, C.- A., Sur la numération factorielle, application aux permutations. Bulletin de la Société Mathématique de France, 16 (1888), p. 176-183] (in French)
* [http://www.dmtcs.org/volumes/abstracts/pdfpapers/dm040203.pdf "A permutation representation that knows what 'Eulerian' means", by Roberto Mantaci and Fanja Rakotondrajao. (PDF)] Description and references for Lehmer codes
* [http://www-ang.kfunigraz.ac.at/~fripert/fga/k1lehm.html A Lehmer code calculator] Note that their permutation digits start from 1, so mentally reduce all permutation digits by one to get results equivalent to the ones on this page.