项目欧拉92

Question

我用来解决问题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

multCoeff是我创建的一个方法，基本上相当于len(set(permutations([int(j) for j in str(i)])))，并且工作得很好。但问题是我得到的结果不正确，看起来我忽略了一些情况，但我真的看不出来是哪些情况。如果有人能指点我方向，我会非常感激。谢谢。

- Hari Seldon

---

你担心将链的数量减少到基本不同的数字，但将具有相同数字平方和的数字合并在一起要快得多。数字的数字平方和的最大值为567，有495个可能的值。只需记住哪些数字导致89，哪些数字导致1即可。 - Douglas Zare

Answer 1

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

您正在尝试通过排除没有按升序排列的数字并在此之后重新计算它们的排列来从 1 到 999,999,999 进行过滤。

您的问题是 0。

根据您的筛选器，2、20、200、2000、20000、200000、2000000 都由 2 表示，但您可能没有添加回这么多的排列。

---

关于您的代码的一般观察：

• item in list 具有 O(n) 的 时间复杂度；尽量避免在大型列表上执行此操作。
• 您正在丢弃许多计算结果；任何导致 89 或 1 结果的链中的任何数字都将始终具有该结束结果。
• 每个函数调用都有时间成本；尽量保持循环调用中的函数数量较少。
• 将 str 转换为 int 有一定的开销；尽量将转换次数保持最少。

- MattH

---

我的程序确实没有计算所有这些排列，我必须考虑这一点。谢谢你的其他建议！ - Hari Seldon