在限制下从int列表生成所有可能的组合 [英] Generate all possible combinations from a int list under a limit

问题描述

我需要在Python中执行此操作. 有一个给定的列表l，可以包含5000多个整数元素. 数字的总和有一个限制，即20000，或者可能很高. 输出应该是从列表中选取的2个数字的所有可能总和， 喜欢，

I need to do this in Python. There is a given list l,may contain more than 5000 integer elements. There is a limit on sum of the numbers,20000 or may be high. The output should be all the possible sums of 2 numbers picked from list, Like,

l=[1,2,3,4,5,6,7,8,9]
output 
1+1,1+2,1+3,1+4,1+5,1+6...........
2+2,2+3,2+4.......
.........
.......

2,3,4,5,6... like that

我正在使用此代码，暂时执行此操作， 但这很慢

I'm using this code,Doing this for now, But It's slow

l=listgen()
p=[]
for i in range(0,len(l)):
    for j in range(i,len(l)):
        k=l[i]+l[j]
        if k not in p:
            p.append(k)
p.sort
print(p)

listgen()是生成输入列表的功能.

listgen() is the function that generating the input list.

推荐答案

某些老式的优化可能会使您的代码更快，比列出具有多个for循环的列表更容易理解:

Some old-fashioned optimization might get you faster code that's easier to grok than list comprehensions with multiple for loops:

def sums(lst, limit):    # prevent global lookups by using a function
    res = set()          # set membership testing is much faster than lists
    res_add = res.add    # cache add method
    for i, first in enumerate(lst):   # get index and item at the same time
        for second in lst[i:]:        # one copy operation saves n index ops.
            res_add(first + second)   # prevent creation/lookup of extra local temporary
    return sorted([x for x in res if x < limit])

print sums(listgen(), 20000)

作为一个额外的奖励，该版本将通过psyco，cython等进行优化.

as an added bonus, this version will optimize beautifully with psyco, cython, etc.

更新: 将其与其他建议进行比较(将listgen替换为range(5000)时，我得到:

Update: When comparing this to the other suggestions (replacing listgen with range(5000), I get:

mine:        1.30 secs
WolframH:    2.65 secs
lazyr:       1.54 secs (estimate based on OPs timings -- I don't have Python 2.7 handy)

这篇关于在限制下从int列表生成所有可能的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！