Python creando una lista con itertools.product?

Question

estoy creando una lista con itertools de una lista de rangos, hasta ahora tengo esto:

start_list = [xrange(0,201,1),xrange(0,201,2),xrange(0,201,5),xrange(0,201,10),xrange(0,201,20),xrange(0,201,50),xrange(0,201,100),xrange(0,201,200)] 

Ahora, sé que si yo fuera a tratar de ejecutar esta línea siguiente que va a matar a mi intérprete de python :

next_list = list(itertools.product(*start_list)) 

lo que me pregunto es ¿sería posible poner en una discusión que comprueba cada tupla, por la suma de sus elementos y sólo los pone en next_list si es igual a una cierta cantidad?

Tal vez algo como:

next_list = list(itertools.product(*start_list,sum(tuples)=200)) 

Sé que esto no es correcto y que podría necesitar para comenzar a volver a pensar en la forma en que voy sobre esto. ¿Los rangos de start_list en el generador serán demasiados para poder construir otra lista?

Answer 1

mejor utilizar sólo una lista comprensión

new_list = [item for item in itertools.product(*start_list) if sum(item) == 200] 

Answer 2

Utilice esta:

next_list = lista (artículo por artículo itertools.product (* START_LIST) si suma (elemento) == 200)

Answer 3

Solution  Runtime   Fn calls   Lines of Code 
-------- ---------- ------------------------ ------------- 
gnibbler 2942.627 s 1473155845 (1.5 billion)   1 
me_A   16.639 s  28770812 (29 million)   5 
me_B   0.452 s  774005 (.8 million)   43 

---

Solución me_A:

import itertools 

def good_combos(basis, addto): 
    good_sums = set(addto-b for b in basis[0]) 
    return ([addto-sum(items)]+list(items) for items in itertools.product(*basis[1:]) if sum(items) in good_sums) 

next_list = list(good_combos(start_list, 200)) 

tenga en cuenta que esto puede ser mucho más rápido si se le pasa la lista más larga primera.

Esta solución reemplaza un nivel de iteración con una búsqueda establecida; con su lista más larga que contiene 200 elementos, no debería sorprender que esto sea casi 200 veces más rápido.

---

Solución me_B:

import itertools 
from bisect import bisect_left, bisect_right 

def good_combos(addto=0, *args): 
    """ 
    Generate all combinations of items from a list of lists, 
    taking one item from each list, such that sum(items) == addto. 

    Items will only be used if they are in 0..addto 

    For speed, try to arrange the lists in ascending order by length. 
    """ 
    if len(args) == 0:       # no lists passed? 
     return [] 

    args = [sorted(set(arg)) for arg in args] # remove duplicate items and sort lists in ascending order 
    args = do_min_max(args, addto)    # use minmax checking to further cull lists 

    if any(len(arg)==0 for arg in args):  # at least one list no longer has any valid items? 
     return [] 

    lastarg = set(args[-1]) 
    return gen_good_combos(args, lastarg, addto) 

def do_min_max(args, addto, no_negatives=True): 
    """ 
    Given 
     args   a list of sorted lists of integers 
     addto   target value to be found as the sum of one item from each list 
     no_negatives if True, restrict values to 0..addto 

    Successively apply min/max analysis to prune the possible values in each list 

    Returns the reduced lists 
    """ 
    minsum = sum(arg[0] for arg in args) 
    maxsum = sum(arg[-1] for arg in args) 

    dirty = True 
    while dirty: 
     dirty = False 
     for i,arg in enumerate(args): 
      # find lowest allowable value for this arg 
      minval = addto - maxsum + arg[-1] 
      if no_negatives and minval < 0: minval = 0 
      oldmin = arg[0] 
      # find highest allowable value for this arg 
      maxval = addto - minsum + arg[0] 
      if no_negatives and maxval > addto: maxval = addto 
      oldmax = arg[-1] 

      if minval > oldmin or maxval < oldmax: 
       # prune the arg 
       args[i] = arg = arg[bisect_left(arg,minval):bisect_right(arg,maxval)] 
       minsum += arg[0] - oldmin 
       maxsum += arg[-1] - oldmax 
       dirty = True 
    return args 

def gen_good_combos(args, lastarg, addto): 
    if len(args) > 1: 
     vals,args = args[0],args[1:] 
     minval = addto - sum(arg[-1] for arg in args) 
     maxval = addto - sum(arg[0] for arg in args) 
     for v in vals[bisect_left(vals,minval):bisect_right(vals,maxval)]: 
      for post in gen_good_combos(args, lastarg, addto-v): 
       yield [v]+post 
    else: 
     if addto in lastarg: 
      yield [addto] 

basis = reversed(start_list) # more efficient to put longer params at end 
new_list = list(good_combos(200, *basis)) 

do_min_max() realmente no se puede lograr cualquier cosa en el conjunto de datos - cada lista contiene 0 y addto, privándola de cualquier apalancamiento - sin embargo, sobre la base más general datos puede reducir en gran medida el tamaño del problema.

Los ahorros aquí se encuentran al reducir sucesivamente el número de elementos considerados en cada nivel de iteración (poda de árboles).