Encontrar combinaciones al valor de sum proporcionado

Tengo series de numeros como esta

myvar = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186] 

Ahora quiero calcular todas estas combinaciones posibles (de longitud 1 a 20) cuya sum es igual a un número dado m .

Intenté resolver con el siguiente código como:

 def sum_count(m): ## Where m is the sum required from itertools import combinations myseq = [] for i in range(1,len(myvar)): mycomb = list(combinations(mass,i)); # Getting combinations of length i mycomb = [list(j) for j in mycomb]; for j in range(len(mycomb)-1,-1,-1): if sum(mycomb[j]) == m: myseq.append(mycomb[j]) return(myseq) 

Cuando pongo m = 270 (por ejemplo) me da:

 [[114, 156], [57, 99, 114]] 

Pero es bastante evidente por parte de myvar que todavía hay otras combinaciones que tienen una sum igual a 270. ¿Dónde no puedo comprender?

TL; DR:

Discuta los diferentes métodos, el mejor método se enumera aquí para facilitar el acceso y fue escrito originalmente por los cuatro ojos :

 def subsets_with_sum(lst, target, with_replacement=False): x = 0 if with_replacement else 1 def _a(idx, l, r, t): if t == sum(l): r.append(l) elif t < sum(l): return for u in range(idx, len(lst)): _a(u + x, l + [lst[u]], r, t) return r return _a(0, [], [], target) 

nota : el método anterior se modifica con mejoras de la versión original a continuación


Mensaje original:

Bien: una aplicación rápida y sencilla de sus datos con cierta lógica concluye que tiene la respuesta correcta:

 # data vals = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186] target = 270 

Usando itertools.combinations :

 >>> from itertools import combinations >>> [comb for i in range(1, 20) for comb in combinations(vals, i) if sum(comb) == target] [(114, 156), (57, 99, 114)] 

Sin embargo, tal vez quiso usar combinations_with_replacement que permite que los valores se usen varias veces desde la lista inicial en lugar de una sola vez.

Usando itertools.combinations_with_replacement :

 >>> from itertools import combinations_with_replacement >>> [comb for i in range(1, 20) for comb in combinations_with_replacement(vals, i) if sum(comb) == target] >>> # result takes too long ... 

Puedes convertirlo en una función robusta:

 def subsets_with_sum(lst, target, subset_lengths=range(1, 20), method='combinations'): import itertools return [comb for i in subset_lengths for comb in getattr(itertools, method)(lst, i) if sum(comb) == target] >>> subsets_with_sum(vals , 270) [(114, 156), (57, 99, 114)] 

Otro método, proporcionado por los cuatro ojos , es mucho más rápido y no requiere importaciones:

 def a(lst, target, with_replacement=False): def _a(idx, l, r, t, w): if t == sum(l): r.append(l) elif t < sum(l): return for u in range(idx, len(lst)): _a(u if w else (u + 1), l + [lst[u]], r, t, w) return r return _a(0, [], [], target, with_replacement) >>> s = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186] >>> a(s, 270) [[57, 99, 114], [114, 156]] >>> a(s, 270, True) [[57, 57, 57, 99], [57, 57, 156], [57, 71, 71, 71], [57, 99, 114], [71, 71, 128], [114, 156]] 

Sincronización:

 def a(lst, target, with_replacement=False): def _a(idx, l, r, t, w): if t == sum(l): r.append(l) elif t < sum(l): return for u in range(idx, len(lst)): _a(u if w else (u + 1), l + [lst[u]], r, t, w) return r return _a(0, [], [], target, with_replacement) def b(lst, target, subset_lengths=range(1, 21), method='combinations'): import itertools return [comb for i in subset_lengths for comb in getattr(itertools, method)(lst, i) if sum(comb) == target] vals = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186] from timeit import timeit print 'no replacement' print timeit("a(vals, 270)", "from __main__ import vals, a", number=10) print timeit("b(vals, 270)", "from __main__ import vals, b", number=10) print 'with replacement' print timeit("a(vals, 270, True)", "from __main__ import vals, a", number=10) print timeit("b(vals, 270, method='combinations_with_replacement')", "from __main__ import vals, b", number=10) 

Salida de tiempo:

 no replacement 0.0273933852733 0.683039054001 with replacement 0.0177899423427 ... waited a long time ... no results ... 

conclusión:

El nuevo método (a) es al menos 20 veces más rápido.

Si simplemente quiere contar el número de combinaciones, use esto:

 aminoacid_masses = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186] def peptides(n, d): for m in aminoacid_masses: if nm in d: d[n] = d.get(n,0)+d[nm] return d def pep_counter(M): dicc = {0:1} mn = min(aminoacid_masses) for i in range(M-mn+1): j = i+mn peptides(j,dicc) return dicc # This line calls the routine and indexes the returned dict. Both with the desired mass (the mass we want peptides to sum up to) print(pep_counter(1024)[1024])