从限制下的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精美优化等等

更新： 在比较这对其他建议（与范围（5000）替换listgen，我得到：

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) 

Answer 2

编辑： Thebjorn说他有最有效的解决方案，我自己的测试同意，虽然我已经改善了我的表现一点。他的代码对Python版本的依赖程度也较低，似乎已经很好地思考并解释了最优化。你应该接受他的回答（并给他upvotes）。

使用itertools.combinations_with_replacement（在python 2.7中添加），并使p a set。

def sums(lst, limit): 
    from itertools import combinations_with_replacement 
    p = set(x + y for x, y in combinations_with_replacement(listgen(), 2)) 
    return sorted([x for x in p if x < limit]) 

你的代码是缓慢的，因为这行：

如果你只是做一些小的改动你的代码，使p是set，这将产生巨大的变化：

L = listgen() 
p = set() 
for i in range(0, len(L)): 
    for j in range(i, len(L)): 
     p.add(L[i] + L[j]) 
print(sorted(p)) 

顺便说一句，这条线在你的例子

p.sort 

没有效果。你必须调用一个方法来实际执行它，就像这样：

p.sort() 

Answer 3

编辑：包括限制（这是不是在OP的代码）。

a = set(x + y for x in l for y in l) 
print(sorted(x for x in a if x < limit)) 

这也降低了算法的复杂性（因为列表中的成员资格测试，您可能会O（n^4））。

Answer 4

如果列表可以包含重复的元素，那么首先摆脱它们可能是明智的想法，例如，通过将列表转换为集合。

Answer 5

如果输入列表已排序，当达到限制时，可以跳出内部循环。另外，制作p一套。

lst=listgen() 
lst.sort() 
p=set() 
for i in range(0,len(lst)): 
    for j in range(i,len(lst)): 
     k=lst[i]+lst[j] 
     if k > limit: 
      break 
     p.add(k) 
p = sorted(p) 
print(p) 

Answer 6

你可以使用 “NumPy的” 这个 这给你definetly的所需的性能：

import numpy as np 

data = np.arange(5000) 
limit = 20000 
result = np.zeros(0,dtype='i4') 
for i in data: 
    result = np.concatenate((result,data[i]+data[i:])) 
    if len(result) >= limit: break 
result = result[:limit] 

编辑： 我只是意识到限制是对总和而不是元素的数量。然后代码应为：

EDIT2： 找到更多的逻辑错误。我的修正建议是：

for idx, x in np.ndenumerate(data): 
    result = np.concatenate((result,x+data[idx[0]:])) 
    if x + data[-1] >= limit: break 
result = result[result <= limit]