python - 我想让 Euler 24 项目的解决方案更有效率

Question

我在 1 分 32 秒内解决了这个问题，这已经很长了。我的解决方案如下。有没有更好的办法解决？

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]

Answer 1

对于您当前的算法，无能为力。 itertools.permutations 函数会更快地完成您为您完成的大部分工作，但这并不有趣。问题的关键在于，通过巧妙的数学运算，您可以在不生成所有排列的情况下找出答案。可以在此处找到对此的示例讨论:http://www.mathblog.dk/project-euler-24-millionth-lexicographic-permutation/