Euler 92项目

Question

我求解problem 92的代码是正确的，但是太慢了，因此我试图修改它，只考虑该数字的每个可能排列的一个数字，有效地将问题的大小从原来的1000万减少到11439。这是我的密码

import time
from Euler import multCoeff

start = time.time()

def newNum(n):
    return sum([int(dig)**2 for dig in str(n)])

def chain(n, l):
    if n in l:
        return n, l
    else:
        l.append(n)
        return chain(newNum(n), l)

nums = []

for i in range(1,10000000):
    if all(str(i)[j] <= str(i)[j+1] for j in range(len(str(i))-1)):
        nums.append(i)

count = 0   

for i in nums:
    if 89 in chain(i,[])[1]: 
        perms = multCoeff(i)
        count += perms

end = time.time() - start            

print count, end

multceff是我创建的一个方法，它基本上等价于len(set(permutations([int(j) for j in str(i)]))) 而且效果很好。不管怎样，问题是我得到的结果不是正确的，看起来我忽略了一些情况，但我真的看不出是哪种情况。如果有人能给我指出正确的方向，我将非常感激。谢谢。在

Answer 1

我们缺少multCoeff的代码，所以我在这里猜测。在

您试图从1到999999999进行筛选，方法是排除没有按升序排列的数字，然后重新计算其排列。在

你的问题是0。在

根据您的过滤器，2, 20, 200, 2000, 20000, 200000, 2000000都是由2表示的，但是您可能没有将这么多排列相加。在

---

对代码的一般观察：

• item in list有O(n)time complexity；尽量避免对大列表这样做。在
• 您正在丢弃许多计算的结果；链中任何一个产生89或{}的数都将得到最终结果。在
• 每个函数调用都有一个时间开销；尽量使循环调用中的函数数保持在较低水平。在
• 将str转换为{}有点昂贵；请尽量将转换的数量保持在最小值。在