Generar todas las combinaciones posibles de una lista int bajo un límite

Question

Necesito hacer esto en Python. Hay una lista dada l, puede contener más de 5000 elementos enteros. Hay un límite en la suma de los números, 20000 o puede ser alto. La salida debe ser todas las posibles sumas de 2 números escogidos de la lista, igual,

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 

estoy usando el código, hacer esto por ahora, pero es lenta

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() es la función que genera la lista de entrada.

Answer 1

Algunos anticuada optimización podría obtener un código más rápido que es más fácil de asimilar que las listas por comprensión con múltiples bucles:

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) 

como un bono adicional, esta versión optimizará la perfección con psyco, Cython , etc.

Actualización: Al comparar esto con las otras sugerencias (en sustitución de listgen con rango (5000), me sale:.

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 dice que tiene la solución más eficiente, y mis propias pruebas concuerdan, aunque he mejorado un poco mi rendimiento. Su código también es menos dependiente de la versión de Python y parece estar muy bien pensado y explicado con respecto a la optimización. Debes aceptar su respuesta (y darle votos a favor).

Use itertools.combinations_with_replacement (agregado en python 2.7), y haga p a .

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

Su código es lento debido a esta línea:

Si usted acaba de hacer un par de pequeños cambios en su código para que p es una set, sería hacer una gran diferencia:

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

Por cierto, esta línea en su ejemplo

p.sort 

no tiene ningún efecto. Debe llamar a un método para ejecutarlo, así:

p.sort() 

Answer 3

Editar: Incluido el límite (que no estaba en el código del OP).

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

Eso también reduce la complejidad del algoritmo (el suyo es potencialmente O (n^4) debido a la prueba de la pertenencia a una lista).

Answer 4

Si la lista puede contener elementos repetidos, puede ser una buena idea deshacerse de ellos primero, p. convirtiendo la lista en un conjunto.

Answer 5

Si la lista de entrada está ordenada, puede salir del bucle interno cuando alcanza el límite. Además, haga p un conjunto.

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

Usted podría utilizar "NumPy" para este Esto le da sin duda el rendimiento requerido:

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: me acabo de dar cuenta que el límite está en el suma y no en la cantidad de elementos. Entonces el código debería leer:

EDIT2: Se encontraron otros errores lógicos. Mi sugerencia es corregido:

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]