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：
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))
最初に最長のリストを渡すと、これがはるかに高速になる可能性があることに注意してください。
このソリューションは、1レベルの反復をセットルックアップに置き換えます。最長のリストに200個のアイテムが含まれているので、これがほぼ200倍高速であることは驚くべきことではありません。
ソリューション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（）は、実際にはデータセットで何も実行できません。各リストには0とaddtoの両方が含まれているため、レバレッジが失われますが、より一般的なデータでは、問題のサイズを大幅に減らすことができます。
ここでの節約は、反復の各レベル（ツリーの剪定）で考慮されるアイテムの数を連続的に減らすことにあります。