// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (20 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 24 Solution

Project Euler 24 Solution

Project Euler 24: Find the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9


Project Euler 24 Problem Description

Project Euler 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?

Analysis

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 as perm
print ''.join(list(perm('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 1 2 3 4 5 6 7 8 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) or ‘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 or ‘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 or ‘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 or ‘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 by removing the placed element from the previous iteration.

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

Project Euler 24
This program and method
solves all test cases for
Project Euler 24 on HackerRank

Project Euler 24 Solution

Runs < 0.002 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 24 Solution Python 2.7 source.

Afterthoughts

Project Euler 24

Project Euler 24 Solution last updated

Discussion

No comments yet.

Post a comment