Problem 24 Project Euler Solution with python

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 how many of you are thinking that this problem will have a very big program. But in the real case this problem has  just 28 lines including the comments. Yes! I am not lying, if you don't believe me then go check the program.

As we are using python it has become easy for us to get the solution. But to be frank we can get even faster solution. To get even faster solution I suggest you to have a look at the following:

1. How to find the rank of a word in a dictionary 
2. Method to find rank of a word 

Even though the faster solution is not exactly the same concept but it is almost the same. I am sure that you will understand the application once you read the concept.

I am not going into any algorithm because the code can simply be called as algorithm(This is also a merit of python 😄).

Program

 Python program is as follows:

If you want to be as simple as possible, then you can write the code as follows:

from itertools import permutations
answer = ''.join(list(permutations('0123456789'))[999999])
print answer

You might have to read the following to understand the program

• Itertools permutations
• Stackoverflow, how to find permutations of a list in python
• Python - convert tuple to string 

If you want to download the source code from here: Github Gist pep24.py

Output

Answer: 2783915460
Execution time: 0.561333179474 seconds
Output:

Project Euler Problem 24 output

Project Euler Problem 24 with answer

Summary

This problem was not really challenging for me because we have solved it with python. I am sure you would have worked hard if you were to solve the same problem with some other programing languages. Thanks to python.

As always if you have any doubt or didn't understand anything, then comment in the comment box below and I will be glad to help you.

please don't hesitate to comment if you have any suggestions or if you have a better program or if you have a different program. Share it with me I will share it with the community😋.

 You can also contact me if you want.

Thank you. Have a nice day🙂.