Geek asks and answers

Generate all possible combinations from the int list under the limit

I need to do this in Python. There is a list l, which can contain more than 5000 integer elements. There is a limit to the sum of the numbers 20,000 or may be high. The result should be all possible sums of two numbers selected from the list, How,

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 use this code doing it now, but it is 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 a function that generates an input list.

+5
source share
6 answers

Some old-fashioned optimization may get faster code that is easier to check than listing lists with several 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 is perfectly optimized using psyco, cython, etc.

Update: ( listgen (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)
+9

EDIT: Thebjorn , , , . python , , . ( ).

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

- :

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

, 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()
+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) - ).

+2

, , . , 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)
+1

"NumPy". :

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]

EDIT: , , . :

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]
+1

, , . .

0

More articles:


All Articles