Factoradic

In combinatorial mathematics, the factoradic is a specially constructed number. 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 . Dr. James McCaffrey has posted an article on MSDN documenting the factoradic index for permutations with supporting code written in C#. The origins of the term 'factoradic' are obscure. In his article he acknowledges Dr. Peter Cameron of Queen Mary, University of London, as having made the original suggestion.

Definition 

factoradic 

the unique factorial-based mixed radix numeral system

radix:       ...     8    7    6   5   4   3   2   1
place value: ...     7!   6!   5!  4!  3!  2!  1!  0!
in decimal:  ...  5040  720  120  24   6   2   1   1

In this numbering system, the rightmost digit may be 0, the next 0 or 1, the next 0, 1, or 2, and so on. The first twenty-four factoradic numbers starting from zero are

decimal  factoradic
  0A            01
  1A          1201
  2A        130201
  3A        131201
  4A        230201
  5A        231201
  6A      14030201
  7A      14031201
  8A      14130201
  9A      14131201
 10A      14230201
 11A      14231201
 12A      24030201
 13A      24031201
 14A      24130201
 15A      24131201
 16A      24230201
 17A      24231201
 18A      34030201
 19A      34031201
 20A      34130201
 21A      34131201
 22A      34230201
 23A      34231201

For another example, the biggest number that could be represented with six digits would be 5₆4₅3₄2₃1₂0₁ which equals 719_A in decimal:

5×5! + 4×4! + 3×3! + 2×2! + 1×1! + 0×0!.

Clearly the next factoradic number after 5₆4₅3₄2₃1₂0₁ is 1₇0₆0₅0₄0₃0₂0₁. But this is equal to 6!, the place value for the radix 7 digit. So the previous number, and its summed out expression above, is equal to:

6! − 1.

It might not be clear at first sight but factorial based numbering system is also unambiguous. No number can be represented by more than one way because the sum of respective factorials multiplied by the index is always the next factorial minus one:

This can be easily proved with mathematical induction.

There is a natural mapping between the integers 0, ..., n! − 1 (or equivalently the factoradic numbers with n digits) 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 Lucas-Lehmer code (inversion table). For example, with n = 3, such a mapping is

 decimal   factoradic     permutation
   0A        030201         (0,1,2)
   1A        031201         (0,2,1)
   2A        130201         (1,0,2)
   3A        131201         (1,2,0)
   4A        230201         (2,0,1)
   5A        231201         (2,1,0)

where the leftmost factoradic digit 0, 1, or 2 selects itself for the first permutation digit from the ordered list (0,1,2) of digits and removes itself from the list, creating a list one shorter missing the first permutation digit. The second factoradic digit if "0" then selects for the second permutation digit the first (0-indexed) digit from the shorter list and removes it, or if "1" selects the second (1-indexed) digit from the shorter list and removes it. The third factoradic digit must be "0", but by now the list is only one item long, so that last remaining item 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 4₇0₆4₅1₄0₃0₂0₁ pick out the digits in the permutation (4,0,6,2,1,3,5).

                                 47064514030201 --> (4,0,6,2,1,3,5)
factoradic:  47         06                       45       14         03         02       01
             |          |                        |        |          |          |        |
    (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 joined using concatenation.

           concatenated
 decimal   factoradics            permutation pair
    0A     030201030201           ((0,1,2),(0,1,2))
    1A     030201031201           ((0,1,2),(0,2,1))
               ...
    5A     030201231201           ((0,1,2),(2,1,0))
    6A     031201030201           ((0,2,1),(0,1,2))
    7A     031201031201           ((0,2,1),(0,2,1))
               ...
   22A     131201230201           ((1,2,0),(2,0,1))
               ...
   34A     231201230201           ((2,1,0),(2,0,1))
   35A     231201231201           ((2,1,0),(2,1,0))

External links

• "Using Permutations in .NET for Improved Systems Security", by Dr. James McCaffrey. Implementation of factoradics in C# source code
• Peter Cameron's Home Page McCaffrey acknowledges Cameron as having first suggested to him using factoradics to index permutations.
• "A permutation representation that knows what 'Eulerian' means", by Roberto Mantaci and Fanja Rakotondrajao. (PDF) Description and references for Lehmer codes
• 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.

See also

• Combinadic
• Factorial