Project Euler 24 Problem Statement

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


Our algorithm recursively calculates the permutations of ever decreasing subsets keeping the sets in lexicographical order. By convention, these permutations count from zero, so we subtract 1 from the target (1,000,000).

Slow and easy itertools version

from itertools import permutations
print ''.join(list(permutations('0123456789',10))[999999])

A more efficient and reasonable approach

Let’s investigate an example, step-by-step, to get an idea of how we can determine our permutation one element at a time.

An example for [A B C D]

The complete lexicographic order for 4 symbols: A, B, C, D
Total permutations = 4! or 3!x4 = 24
     Col 0          Col 1          Col 2          Col 3
00 [A B C D]   06 [B A C D]   12 [C A B D]   18 [D A B C]
01 [A B D C]   07 [B A D C]   13 [C A D B]   19 [D A C B]
02 [A C B D]   08 [B C A D]   14 [C B A D]   20 [D B A C]
03 [A C D B]   09 [B C D A]   15 [C B D A]   21 [D B C A]
04 [A D B C]   10 [B D A C]   16 [C D A B]   22 [D C A B]
05 [A D C B]   11 [B D C A]   17 [C D B A]   23 [D C B A]

Let’s find the 10th lexicographic permutation (index 9 starting from zero or the 10th entry). The data is arranged in a rectangular grid 3! rows by 4 columns, i.e. 6×4.

If we just want the first number for the 10th arrangement we can see it’s in column 1, which makes sense because the first 3! arrangements will start with ‘A’ the second 3! with ‘B’ and so on. So, to calculate the column we simply integer divide our desired index, 9, by 3! which equals 1.

The column and the first element of our 10th lexicographic permutation:
9/3! = 1 with 3 remainder. That is, column 1 which all start with ‘B’. ‘B‘ is the first element.

Now let’s create a new table without ‘B’ since it has now been placed in the first position:

The complete lexicographic order for 3 symbols: A, C, D
Total permutations = 3! or 2!x3 = 6
   Col 0        Col 1        Col 2 
00 [A C D]   02 [C A D]   04 [D A C]
01 [A D C]   03 [C D A]   05 [D C A]

Remember our remainder of 3 from the previous calculation? Well, that’s now our new index for the next element.

3/2! = 1 with 1 remainder. That is, column 1 which all start with ‘C’. ‘C‘ is the second element.

Let’s do this one last time:

The complete lexicographic order for 2 symbols: A, D
Total permutations = 2! or 1!x2 = 2
  Col 0      Col 1
00 [A D]   01 [D A]

Again, recall our remainder of 1 from the previous calculation.

1/1 = 1 with 0 remainder. That’s column 1 or ‘D‘ and the last dependent position will be filled by ‘A‘. Our 10th lexicographic permutation is [B C D A].

Testing this algorithm on Project Euler 24

Now, using this algorithm, lets get the first 4 digits to the millionth lexicographic permutation of the digits 0 through 9.
[0 1 2 3 4 5 6 7 8 9]
First digit: 999999/9! = 2 with 274239 remainder. First digit is at index 2 (starting from 0) = ‘2
2 [0 1 3 4 5 6 7 8 9]
Second digit: 274239/8! = 6 with 32319 remainder. Second digit is at index 6 = ‘7
2 7 [0 1 3 4 5 6 8 9]
Third digit: 32319/7! = 6 with 2079 remainder. Third digit is at index 6 = ‘8
2 7 8 [0 1 3 4 5 6 9]
Fourth digit: 2079/6! = 2 with 639 remainder. Fourth digit is at index 2 = ‘3
2 7 8 3 [0 1 4 5 6 9]

This method lends itself to recurrence nicely by building the result one element at a time. It will recursively call itself each time reducing the size of the set by 1. The placed element from the previous iteration will be removed.

HackerRank version

Even though HackerRank steps up the challenge by increasing the set to 13 characters and proving 1000 trials, this algorithm still solves them in one-thousandth of a second.

Python 2.7 Source

Last Word

  • You can learn more about this method by visiting Factorial number system on Wikipedia.
  • You can change the character set from “0123456789” to “abcdefghijklm” to test the HackerRank parameters.