Python-erstellen einer Liste mit itertools.Produkt?

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

Lösung 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))

Tun, beachten Sie, dass dies viel schneller, wenn Sie übergeben es der längste Liste erste.

Diese Lösung ersetzt eine Stufe der iteration mit einer set-lookup, mit der längsten Liste mit 200 Elemente, sollte es nicht überraschen, dass das fast 200-mal schneller.

Lösung 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() kann nicht wirklich etwas erreichen, auf Ihre Daten-set - jede Liste enthält sowohl 0 als auch addto zu berauben, eine Hebelwirkung - aber auf allgemeiner basis von Daten kann erheblich reduzieren das problem der Größe.

Die Einsparungen, die hier zu finden sind sukzessive reduziert die Anzahl der Elemente in jeder Stufe der iteration (Baumpfleger).