Factorial Number System & Permutations

July 28, 2010 - 13:42

The other day, while working on my survey of register allocation based software watermarking techniques, I learnt something new about numbers: the factorial number system. This number system is useful for finding permutations of lexicographically ordered sets.

base: 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

 

For example, to convert the decimal number 22 into the factorial number system:

2210 = 3 * 6 + 2 * 2 + 0 * 1 + 0 * 0 = 3200!

To find the 22nd permutation of {1,2,3,4}, each of the factorial number digits acts as an index (starting at position 0) which shows the number to remove next to build up the permutation set. 

factoradic:  3          2      0        0
             |          |      |        |
      (1,2,3,4) -> (1,2,3) -> (1,2) -> (2)
             |          |      |        |
permutation:(4,         3,     1,       2)

The 22nd permutation is therefore {4,3,1,2}.