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
Solution 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))
Do note that this can be much faster if you pass it the longest list first.
This solution replaces one level of iteration with a set lookup; with your longest list containing 200 items, it should not be surprising that this is almost 200 times faster.
Solution 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() really can't accomplish anything on your data set - each list contains both 0 and addto, depriving it of any leverage - however on more general basis data it can greatly reduce the problem size.
The savings here are found in successively reducing the number of items considered at each level of iteration (tree pruning).
