Project Euler Problem 24 Solution

Project Euler & HackerRank Problem 24 Solution

Lexicographic permutations
by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank

Project Euler Problem 24 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 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

Dilbert cartoon on permutations

Solving this problem and studying the second solution below can help you understand the recursive process. The first solution is effective but lacks the scope to solve the HackerRank version. Also, 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]

Our goal is to 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 remainder 3 . That is, column 1 which all start with 'B'. 'B' is the first element.

Now, 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 remainder 1. That is, column 1 which all start with 'C'. 'C' is the second element.

And now to finish:

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 remainder 0. 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, let’s 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 remainder 274239. 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 remainder 32319. Second digit is at index 6 = '7'
2 7 [0 1 3 4 5 6 8 9]
Third digit: 32319/7! = 6 with remainder 2079. Third digit is at index 6 = '8'
2 7 8 [0 1 3 4 5 6 9]
Fourth digit: 2079/6! = 2 with remainder 639. 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

HackerRank steps up the challenge by increasing the set from 10 to 13 characters (a–m) and proving 1000 trials by finding the Nth lexicographic permutation, 1 ≤ N ≤ 13! (or 6,227,020,800).

Python Source Code

Last Word