Generowanie wszystkich możliwych kombinacji z listy int pod limitem

Question

Potrzebuję zrobić to w Pythonie. Istnieje podana lista l, może zawierać ponad 5000 elementów całkowitych. Istnieje limit na sumę liczb, 20000 lub może być wysoki. Wyjście powinno być wszystkie możliwe sumy 2 liczb wybrał z listy, podobnych,

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 

używam tego kodu, robią to teraz, ale to powolny

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() jest funkcją generującą listę wejściową.

Answer 1

Niektóre staromodny optymalizacja może Ci szybszy kod, który jest łatwiejszy do grok niż listowych z wielu pętli:

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) 

jako dodatkowy bonus, ta wersja będzie pięknie optymalizacji z psyco, Cython itp.

Aktualizacja: Porównując to z innymi sugestiami (zastępujący listgen z zakresu (5000), otrzymuję.

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

EDYCJA: Thebjorn mówi, że ma najbardziej wydajne rozwiązanie, a moje własne testy są zgodne, chociaż trochę poprawiłem swoją wydajność. Jego kod jest również mniej zależny od wersji Pythona i wydaje się być bardzo dobrze przemyślany i wyjaśniony w odniesieniu do optymalizacji. Powinieneś przyjąć jego odpowiedź (i dać mu przegraną).

Użyj itertools.combinations_with_replacement (dodane w python 2.7) i wykonaj 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]) 

Twój kod jest powolne z powodu tej linii:

Jeśli po prostu zrobić kilka drobnych zmian w kodzie, tak że p jest set, że zrobi to ogromna różnica:

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

Nawiasem mówiąc, ta linia w Twojej przykład

p.sort 

nie daje efektu. Musisz wywołać metodę, aby faktycznie go wykonać, tak jak:

p.sort() 

Answer 3

Edytuj: Uwzględniono limit (który nie znajdował się w kodzie OP).

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

To również zmniejsza złożoność algorytmu (twoje jest potencjalnie O (n^4) z powodu testowania członkostwa na liście).

Answer 4

Jeśli lista może zawierać powtarzające się elementy, dobrym pomysłem jest najpierw ich pozbyć się, np. konwertując listę do zestawu.

Answer 5

Jeśli lista wejściowa jest posortowana, po osiągnięciu limitu można przerwać pętlę wewnętrzną. Ustaw również zestaw 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

Można użyć "NumPy" dla tego To daje zdecydowanie wymagana wydajność:

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: zdałem sobie sprawę, że granica jest na suma, a nie liczba elementów. Następnie kod powinien brzmieć:

EDIT2: Znaleziono dalsze błędy logiczne. Moja sugestia jest poprawione:

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]