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

发布时间：2020-12-20 11:39:34 所属栏目：Python 来源：网络整理

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

想象一下,你试图在某些领域(例如t = 5)分配一些固定资源(例如n = 10).我试图有效地找出如何获得总和为n或更低的所有组合.

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

我到目前为止：

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

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

计时(1000次迭代)：

Default (itertools.product)           --- time: 40.90 s
falsetru recursion                    --- time:  3.63 s
Aaron 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 lst

t = 5
n = 10
for xs in f(range(n+1),5):
    print xs

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!