从限制下的int列表生成所有可能的组合

Question

我需要在Python中执行此操作.有一个给定的列表l,可能包含超过5000个整数元素.数字之和有限,20000或可能很高.输出应该是从列表中选取的2个数字的所有可能总和,比如,

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

我正在使用这段代码,现在就这样做,但它很慢

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() 是生成输入列表的函数.

Answer 1

一些老式的优化可能会让你获得更快的代码,比使用多个for循环的列表理解更容易理解:

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等精美优化.

更新: 将此与其他建议进行比较(将rangegen替换为范围(5000),我得到:

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)