Project Euler Problem 24 Solution

Project Euler Problem 24 Solution

Lexicographic permutations

by {BetaProjects} | 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
# Find the one millionth permutation of '0123456789'
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 00         Col 01         Col 02         Col 03
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 of 3! rows by 4 columns, i.e. 6×4.

When finding the first element in the 10th arrangement, we can see it's in column 01. This makes sense because the first 3! (6) arrangements start with 'A', the next 6 arrangements start with 'B', and so on.

The column and the first element of our 10th lexicographic permutation:
9/3! = 1 with remainder 3. That is, column 01 which all starts 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 00       Col 01       Col 02
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 01 which all starts 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 00     Col 01
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 01 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 logo

Solves all test cases for Hackerrank Project Euler Problem 24

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

Python Source Code

import math
def perm(n, s):
   if len(s)==1: return s
   q, r = divmod(n, math.factorial(len(s)-1))
   return s[q] + perm(r, s[:q] + s[q+1:])
for _ in range(int(input())):
    print(perm(int(input())-1, 'abcdefghijklm'))

Last Word