11

我正在从范围列表中创建一个带有 itertools 的列表,到目前为止我有这个:

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

现在,我知道如果我尝试运行下一行,它会杀死我的 python 解释器:

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

我想知道的是是否可以放入一个参数来检查每个元组,检查其项目的总和,如果等于一定数量,则仅将它们放入next_list中?

也许是这样的:

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

我知道这是不对的,我可能需要开始重新考虑我的处理方式。生成器中 start_list 的范围是否会太多而无法构建另一个列表?

4

3 回答 3

19

最好只使用列表理解

new_list = [item for item in itertools.product(*start_list) if sum(item) == 200]
于 2012-06-12T02:00:05.060 回答
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

解决方案我_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))

请注意,如果您首先将最长的列表传递给它,这会更快

该解决方案用集合查找替换了一级迭代;最长的列表包含 200 个项目,这几乎快 200 倍也就不足为奇了。


解决方案我_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,从而剥夺了它的任何影响力-但是在更一般的数据基础上,它可以大大减少问题的大小。

此处的节省在于连续减少在每个迭代级别(树修剪)考虑的项目数量。

于 2012-06-12T17:53:39.160 回答
1

用这个:

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

于 2012-06-12T01:45:29.763 回答