# Project Euler 24 Solution: Lexicographic permutations

Problem 24

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

## Solution

This problem can be solved trivially with a loop that runs a million times and permutates an array with the digits from 0 to 9 using a library function like itertools permutation. However, let's analyze the problem mathematically. My first idea was to put the beginning state into an array and simply add a million in a certain base, the same way a big integer library works. However, when playing around with the numbers, the base doesn't remain constant and is different for every position.

A number system with base $$b$$ normally has $$b^k$$ possible permutations between zero and $$b^k-1$$. For example in base two there are 512 numbers between 0 and 511. Here things are getting interesting. For our problem every position $$k$$ in the number is $$k!$$. That means that the last nine digits can be ordered in 9! ways and that the first digit will be a zero for the first $$9!$$ permutations, a one for numbers between $$9!+1$$ to $$2\cdot 9!$$ and so on. Based on that we can see already that the millionth permutation will start with a 2.

This is really cool, I looked that up. The name of a number system that is formed based on factorials instead of powers is called Factorial number system. All that we need to do now is implementing a base-converter from base 10 to factorial base. As we need only the first 10 factorials, I store them into an array to keep the code small:

var fac = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880];

function solution(num) {

var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var ret = "";

num--;
for (var i = arr.length - 1; i >= 0; i--) {
var t = num / fac[i] | 0;
num%= fac[i];
ret+= arr[t];
arr.splice(t, 1);
}
return ret;
}

solution(1e6);

« Back to problem overview