# 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.