如何在Python中有效地获得总和为10或更低的所有组合

概述想象一下,你试图在某些领域(例如t = 5)分配一些固定资源(例如n = 10).我试图有效地找出如何获得总和为n或更低的所有组合. 例如. 10,0,0,0,0是好的,以及0,0,5,5,0等,而3,3,3,3,3,3显然是错误的. 我到目前为止： import itertoolst = 5n = 10r = [range(n+1)] * tfor x in itertools.prod 想象一下,你试图在某些领域(例如t = 5)分配一些固定资源(例如n = 10).我试图有效地找出如何获得总和为n或更低的所有组合.

例如. 10,0是好的,以及0,5,0等,而3,3,3显然是错误的.

我到目前为止：

import itertoolst = 5n = 10r = [range(n+1)] * tfor x in itertools.product(*r):    if sum(x) <= n:                 print x

然而,这种蛮力方法非常缓慢;肯定有更好的办法？

计时(1000次迭代)：

Default (itertools.product)           --- time: 40.90 sfalsetru recursion                    --- time:  3.63 sAaron Williams Algorithm (impl,Tony) --- time:  0.37 s

解决方法 创建自己的递归函数,除非可以得到一个< = 10的总和,否则不会使用元素递归.

def f(r,n,t,acc=[]):    if t == 0:        if n >= 0:            yIEld acc        return    for x in r:        if x > n:  # <---- do not recurse if sum is larger than `n`            break        for lst in f(r,n-x,t-1,acc + [x]):            yIEld lstt = 5n = 10for xs in f(range(n+1),5):    print xs

总结

以上是内存溢出为你收集整理的如何在Python中有效地获得总和为10或更低的所有组合全部内容，希望文章能够帮你解决如何在Python中有效地获得总和为10或更低的所有组合所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。