Project Euler Solution #24: 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);