Does python create a list with itertools.product?

Question

I am creating a list with itertools from a list of ranges, as long as I have it:

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

Now I know that if I tried to run the following line, it would kill my python interpreter:

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

What interests me is whether it is possible to insert an argument that checks each tuple into the sum of its elements and put them only in next_list if it is equal to a certain sum?

Maybe something like:

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

I know this is wrong, and I may have to think about how I do it. Will the start_list range in the generator be too long to go through to create another list?

Answer 1

Better to just use list comprehension.

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

Answer 2

 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 

---

Me_A solution:

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

Note that this can be much faster if you give it the longest list at the beginning .

This solution replaces one level of iteration with an installation search; with your longest list containing 200 items, no wonder it's almost 200 times faster.

---

Me_B solution:

 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 () really can do nothing in your data set - each list contains both 0 and addto, deprives it of any leverage, however, on more general basic data, it can significantly reduce the size of the problem.

The savings here are determined by a sequential decrease in the number of elements considered at each iteration level (tree pruning).

Answer 3

Use this:

next_list = list (item for an item in itertools.product (* start_list), if sum (position) == 200)