Problem #24 is similar to Problem #15 in that they both commonly appear on introductory math competitions such as the AMC 10/12 and Mathcounts. However, unlike Problem #15, this question is pretty annoying. The question reads:
Project Euler Problem 24: Lexicographic permutations
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?
I don’t know why, but I’ve always found this problem to be incredibly annoying as you are very susceptible to “off by one” errors while solving it. Here’s my solution:
Solution #1: Brute Force Approach
The key is to notice that there are precisely 9! (9 factorial) permutations that begin with 0, 9! that begin with 1, and so on, with each starting digit getting exactly 9! permutations. Once a starting digit is chosen, the problem reverts to a version with 1 less potential digit (but the index of the permutation decreases based on the starting digit).
A starting digit of 0 covers permutations 1 – 9!, a starting digit of 1 covers permutations 9!+1 – 2*9!, and so on. I found this pretty annoying, so I shifted my solution (and the problem) to a 0-based index where by decreasing the index (1,000,000) by 1, I could instead say that 0 covers permutations 0 – (9!-1), 1 covers permutations 9! – (2*9!-1), and so on. After making this change, I just repeatedly used the first observation to find each digit moving from left to right. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #24
'''
import time
def factorial(n):
total = 1
for c in range(2,n+1):
total*=c
return total
def projectEulerProblemTwentyFour(n, x):
myFactorials = []
for i in range(x):
myFactorials.append(factorial(x-1-i))
myString = ""
n-=1
counter = 0
possibleDigits = []
for i in range(x):
possibleDigits.append(str(i))
while(counter<x and len(possibleDigits)>1):
total = 0
thisDigit = -1
while(total<=n):
total+=myFactorials[counter]
thisDigit+=1
myString += possibleDigits[thisDigit]
n-=(total-myFactorials[counter])
possibleDigits.pop(thisDigit)
counter+=1
myString+=possibleDigits[0]
return myString
start = time.time()
print projectEulerProblemTwentyFour(1000000, 10)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
2783915460
--- 2.90870666504e-05 seconds ---
for input of n = 1000000, x = 10
'''
And with that, we’re done with this very annoying problem. It always takes me a bit of troubleshooting to solve this problem, so I’m glad I got it done.
Thanks for reading!
The Inner Machinations of Walker 