Stack Exchange
I want to make my solution for project Euler 24 more efficient
I solved the question in 1 min 32 seconds which is a lot. My solution is below. Is there a better way to solve it?
def fill_in(letter, word):
    perm = []
    for i in xrange(len(word)+1):
        the_word = word[0:i] + letter + word[i:]
        if the_word[0] == '2':
            perm.append(the_word)
    return perm

def perm(string):
    "Find all permutations of given string"
    perm_list = []
    for i in string:
        if len(perm_list) == 0:
            perm_list.append(i)
        else:
            temp = []
            while (len(perm_list) != 0):
                temp = temp + fill_in (i, perm_list.pop())
            perm_list = temp
    return perm_list





j = perm("2013456789")
j.sort()
print j[1000000-725760-1]


As you've found here -- many Project Euler questions admit a brute force solution that's exponentially too slow. The challenge isn't to code the brute force solution in an efficient way (although occasionally that works), it's to find a mathematical or computer science technique to produce an efficient-enough solution. Asking other people for the best way to solve the puzzle is like asking someone else for the best move in a game of chess -- you might be moving the pieces, but you're not playing chess.

Here's a simple code that provides answer in an instant:
from math import factorial

digits = range(10)
res = []
n = 999999 # PE uses 1-based indexing

for i in xrange(len(digits) - 1, -1, -1):
    index, n = divmod(n, factorial(i))
    res.append(digits.pop(index))

print ''.join(str(i) for i in res)

It's based on factorials and the principle is really simple. Let's say you have digits 1234 which results to 4! permutations. 3! first permutations start with 1 so you can get the index of first digit simply by dividing permutation number with 3!. Then remove the digit from available digits and add it to the result. For the following digits use remainder of previous division as permutation number.

Why does this work, and what if n is smaller than the length?

@JohnnyApple: If you change n to 0 and run the code you can see that the output is the same as digits. It works because for n items there are (n - 1)! permutations starting with each item.

For your current algorithm, not much can be done. The itertools.permutations function will do most of what you've done for you somewhat faster but that's no fun. The point of the question is that with clever maths you can figure out the answer without generating all the permutations. An example discussion of this can be found here: http://www.mathblog.dk/project-euler-24-millionth-lexicographic-permutation/

def permutation(order):
    start = time.time()
    digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]  # our main list.
    original_digits = digits.copy()  # take a shallow copy of the list.
    i = 1
    result = 0
    wanted_num = ""
    while i <= len(original_digits):
        x = 0
        while True:
            # removing the number of redundant possibilities.
            result += factorial(len(original_digits) - i)
            x += 1
            if result > order - 1:
                result -= factorial(len(original_digits) - i)
                x -= 1
                wanted_num += str(digits[x])
                digits.remove(digits[x])  # prevent repetition.
                break
        i += 1
        if result == order and len(digits) == 0:
            break
    return int(wanted_num), time.time() - start

Use the following line to test it:
print(permutation(1000000))

