Generate all possible combinations from a int list under a limit

Question

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() is the function that generating the input list.

Answer 1

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)

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

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)

Answer 2

EDIT: Thebjorn says he has the most efficient solution, and my own tests agree, though I've improved my performance a little. His code is also less dependent on python version and seems to be very well thought out and explained with regards to optimalization. You should accept his answer (and give him upvotes).

Use itertools.combinations_with_replacement (added in python 2.7), and make 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])

Your code is slow because of this line:

if k not in p: # O(N) lookup time in lists vs average case O(1) in sets

If you just make a couple of small changes to your code so that p is a set, it would make a huge difference:

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))

By the way, this line in your example

p.sort

has no effect. You must call a method to actually execute it, like so:

p.sort()