Factorial base numbers and permutations

Jul 22, 2012   #algorithms

This is something I came across while doing a project euler problem. The problem is asking us to find the millionth lexicographic permutation of the digits 0 to 9. After solving the problem by writing a function that generates the next permutation of a number and calling it 999,999 times, I was browsing the thread with other people’s solutions, and came across someone who used factoradic numbers to solve it. I was curious as I had never heard of this number system before and had no idea how it can be used to generate the millionth lexicographic permutation of a set of numbers.

The idea behind factoradic numbers is the following: the $i^{th}$ number from the right has base $i$.

This sounds simple, but I had to rethink how numbers work to really understand it. In constant base numbers, which we’re used to, the $i^{th}$ digit from the right has a place value of $base^{i-1}$. But in factoradic the $i^{th}$ digit from the right has a place value of $(i-1) !$. Why is that so?

How base ten numbers work

In decimal, if we had just one digit, we could only represent the numbers from $0$ to $9$. If we wanted to keep counting further than $9$, we need another, different kind of digit, that we would use to count the number of Tens.

Why Tens though and not Nines or Elevens? Because $10$ is $1$ more than the maximum value we could represent with the previously existing digits. If we decided to count the number of Nines instead with that new digit, then we would end up with two different representations for the number nine: $09$ and $10$ would be the same. On the other hand, if we decided to count the number of Elevens with that new digit, then we would have no way to represent the number ten.

So now we have two digits, each one with $10$ possible values and we can represent up to $10*10$ different numbers, from $0$ to $99$. If we wanted to keep going further, we would have to add another yet different kind of digit to count the $100$s, and so on.

How factorial base numbers work

Let’s adapt that to factoradic. The first digit has base $1$, with only one possible value: $0$ and we can’t count anything with it, as it can only be zero. Then we add a new kind of digit to count the number of zeros. But this new digit will have a different base: base $2$. So it has two possible values: $0$ and $1$. As we have a digit with $2$ possible values, and another with $1$ possible value, we can create a total of $2*1 = 2 !$ different numbers. Their values range from $0$ to $2 !-1$.

If we want to count further we add another digit, which has base $3$ this time, and possible values: $0$, $1$, $2$. With this digit, we will count the number of $2 !$s, which is the previously maximum representable value plus $1$. Now we can represent $3*2*1 = 3 !$ different numbers ranging from 0 to $3 !-1$. And so on.

In summary:

• The $i^{th}$ digit from the right has place value $(i-1)!$ as it counts the number of $(i-1)!$s.
• The maximum value we can represent with n digits is : $(n-1) * (n-1)! + (n-2) * (n-2)! + … + 3 * 3! + 2 * 2! + 1 * 1!$
• To convert a 7 digit number like $4533210$ from factoradic to decimal we do $4 * 6! + 5 * 5! + 3 * 4! + 3 * 3! * 2 * 2! + 1 * 1! + 0 * 0! = 3575$

Another fact which makes this number system work is that

$$\sum_{i=0}^{n} i*i! = (n+1)! - 1$$

which means that the biggest number we can represent with $n$ digits in factoradic is equal to the smallest number we can represent with $n+1$ digits minus $1$. This establishes that there is a unique representation for every integer in factoradic.

This can be proven by noticing that $\forall i, i*i! = (i+1 -1)*i! = (i+1)! - i!$: subsequent terms cancel each other, leaving the first and last term.

The reason factoradic numbers are relevant to the permutations problem on project Euler is that there is a natural mapping between the numbers with $n$ digits in factorial representation and the permutations of $n$ elements in lexicoraphical order.

A permutation of a set of objects is a rearrangement of these objects into a particular order. The $n^{th}$ lexicographic permutation can be found by generating all the permutations of that set of objects, then sorting them alphabetically and picking the $n^{th}$.

For example, the set $\{ 0, 1, 2 \}$ has $3!$ permutations. In lexicographical (or alphabetical) order, they are the following:

Lexicographic permutation Index (decimal) Index (factoradic)
$012$ $0$ $000$
$021$ $1$ $010$
$102$ $2$ $100$
$120$ $3$ $110$
$201$ $4$ $200$
$210$ $5$ $210$

The amazing thing is that there is a way to calculate a permutation by its index without enumerating all the previous ones! Let’s say we want to know what is the $4^{th}$ lexicographical permutation of the digits in the set $\{0, 1, 2\}$. That is, the permutation with index $3$ in the table above, as they are zero indexed.

The first thing to do is convert decimal $3$ to its factoradic representation and get $110$. Then we create a list of the set elements in lexicographic order and follow these steps:

Available set elements in lexicographic order {0, 1, 2}
Permuation ?

The leftmost digit of the factoradic number, is the same as the leftmost digit of the permutation. In our case that’s $1$. We use this digit as the first digit of the permutation, and delete it from the set of available elements.

Available set elements in lexicographic order {0, 1, 2}
Permuation 1..

Now our available set elements are {0, 2} and the unused digits in the factoradic number are 110.

Now the amazing thing is that if we view the set of available set elements $\{0, 2\}$ as a zero-indexed list, and if we view the remaining digits in the factoradic number 110 as indices to this list, then each successive digit of the factoradic number defines the next number of the permutation!

So, looking at the factoradic number 110 the next digit to use is 1, which means that the next number in the permutation is the number with index 1 from the set {0, 1, 2}. That is 2. We add this number to the permutation, delete it from the set elements, and mark it as used in the factoradic number. Now we have:

Available set elements in lexicographic order {0, 1, 2}
Permuation 12..

Looking at the factoradic number 110 the next digit in the permutation is the one with index 0 in the list {0, 1, 2}. That is 0. We delete this element from the set and put it in the permutation.

Available set elements in lexicographic order 0, 1, 2}
Permuation 120

And that’s it! We calculated that the permutation with index $3$ is $120$, and did so without enumerating all the previous permutations. We can verify our answer by looking at the first table above.

Converting decimal to factorial base

When we did the conversion above, the first step was to convert the index of the desired permutation from decimal to factorial base. But how do we do that?

It turns out that the old method of successive integer divisions by the place value for each positions till works.

Here’s an example. We’ll convert $81$ decimal to factoradic. $81$ is less than $5!$ (which equals $120$) but more than $4!$ (which equals $24$) which means it should be possible to represent it using $5$ digits in factoradic, because the $i^{th}$ digit from the right has place value $(i-1)!$

Since our number has $5$ digits, it is of the form $d4 * 4! + d3 * 3! + d2 * 2! + d1 * 1! + d0 * 0!$

Performing successive divisions by the place value for each position we get:

$$81 = \underline{3} * 4! + 9$$ $$9 = \underline{1} * 3! + 3$$ $$3 = \underline{1} * 2! + 1$$ $$1 = \underline{1} * 1! + 0$$ $$0 = \underline{0} * 0! + 0$$

So the result is $31110$ in factoradic.

To double check the result let’s convert back to decimal:

$3*4! + 1*3! + 1*2! + 1*1! + 0*0!$ equals $81$ indeed.

So how can we find the millionth permutation without finding the first 999,999 permutations first?

Going back to the original problem of finding the millionth lexicographic permutation of the digits $0-9$, now with our factoradic conversion skills we can find the answer by doing something like:

permutationByFactoradicIndex(decimalToFactoradic(1,000,000 - 1), sortedSetElements)

We just need to write these two functions.

References:

http://en.wikipedia.org/wiki/Factorial_number_system