蟒蛇lambda可以用来改变另一个函数的内部工作吗？

Question

我有以下代码片段,我需要(大规模)加速.它是非常低效的.

possible_combos.append([comb for comb in
    itertools.combinations_with_replacement(input_list, target_number_of_packages)
        if np.sum([j[1] for j in comb])==target_number_of_packages])

拆解:

possible_combos 

是输出

input_list

是一个元组列表([...],number_of_packages)

target_number_of_packages

是我需要达到的包数.我可以根据需要组合列表"input_list"的多个元素(允许重复),但是在添加"number_of_packages"时需要准确到达target_number_of_packages,否则组合无效.

我在考虑类似的事情

possible_combos.append([comb for comb in
    itertools.combinations_with_replacement(input_list, lambda x:x=...)))

但无法填补空白.

我的问题是,是否可以这样使用lambda？我不需要如何处理这个特定用例的答案,因为我已经解决了不同的问题(使用itertools产品作为递归生成器函数),但我仍然想知道,是否有解决方案？

简而言之:是否有可能使用lambda来改变另一个函数内的值对飞？

问题的最小例子:

input_list=[1,2,3,4,5,6] #in minmal form

target_number_of_packages=4

possible_combos should be [[1,1,1,1],[2,1,1],[2,2],[3,1],[4]]

我正在寻找大致相当于,但速度快于的东西,

possible_combos=[comb for comb in
    itertools.combinations_with_replacement(input_list) if np.sum(comb)==target_number_of_packages]

只需将np.sum(comb)== target放入itertools.combinations_with_replacement中 - 如果可能的话.

我已经改变了这个问题,因为我以不同的方式解决了潜在的问题,但其中的一部分仍然是我想知道的.由于没有答案,我认为编辑是适当的.

Answer 1

lambda只是语法，允许您在表达式中创建函数对象（def functionname(..): ...是语句，并且不能在表达式内使用语句）。所以 lambda 只是创建一个函数对象，并没有什么特别的。您不能使用函数在运行时更改另一个函数的本地命名空间，不是。

从评论来看，您似乎在询问如何使用回调来解决您的问题，但我认为您还没有完全理解您的问题空间，也没有完全理解事情是如何list.sort(key=...)工作的。Python 的排序实现显式调用回调key，通过选择，调用的函数会传递信息，排序函数会根据返回的内容改变行为；key 函数无法选择返回值会发生什么。

我认为你在这里问了错误的问题。

您试图解决背包问题的子集的问题；你有无限的变体，因为我可以根据需要组合列表“input_list”中任意多个元素（允许重复）。

试图用itertools问题去解决是错误的做法；itertools函数会生成许多不正确的组合。您实质上是为输出大小 1 到目标大小生成具有重复 ( multisets ) 的所有组合，因此您可以计算每个给定大小的此类多重集的数量，并对它们求和：

def multiset_size(n, k):
    return int(factorial(k + n - 1) / (factorial(k) * factorial(n - 1)))

generated = sum(multiset_size(len(input_list), i + 1) for i in range(target_number_of_packages))

对于您的玩具示例，有 6 个输入且目标大小为 4，您将生成 209 种不同的组合，但只有 5 种可行的组合。每个可行输出浪费了40.8 个组合！输入尺寸越大，这个比率只会变得（更）差。

完整的背包问题通常使用动态规划方法来解决。编程chrestomathy网站Rossettacode.org 有一个很棒的 Python 示例，介绍如何使用 DP 实现无界背包解决方案。基本上，您为每个容量级别（从零到最大）保留一个“麻袋”表，并保持该表更新，因为您会看到将当前项目添加到有空间容纳该项目的麻袋中是否会产生更好（更有价值）的麻袋比迄今为止该麻袋的最佳组合。

但是，当生成所有可能的组合时，您最好使用自己的迭代或递归方法。这里没有可以使用的现成itertools函数，使用回调函数也不会让这变得更容易。

借鉴 DP 解决方案，迭代解决方案将为每个可能的总容量使用一系列麻袋堆，并在向每个有空间容纳它们的麻袋中添加更多此类物品时将它们复制到下一堆：

from itertools import repeat

def unbounded_knapsack_combos(input_list, target):
    # collect piles of filled sacks, here each pile contains
    # all sacks of the same capacity.
    # A sacks consist of counts for each item in input_list, so
    # sack[0] counts how many input_list[0] items were used.
    # piles start empty, except for pile 0 (the empty sack pile)
    piles = [[] for _ in range(0, target)]
    piles[0] = [[0] * len(input_list)]

    # process from smallest to biggest so we can avoid some work, like
    # adding an item of size target - 1 on a pile that will never combine
    # with larger items
    size_idx = [(s, i) for i, (_, s) in enumerate(input_list) if s <= target]
    for size, i in sorted(size_idx):
        for s in range(size, target + 1 - size):
            for sack in piles[s - size]:
                new_sack = sack[:]
                new_sack[i] += 1
                piles[s].append(new_sack)

        # Yield knapsacks that can be completed
        for sack in piles[target - size]:
            new_sack = sack[:]
            new_sack[i] += 1
            # turn the item counts in each sack in the target pile back into
            # items from the input list
            yield [item for i, c in enumerate(new_sack) if c
                   for item in repeat(input_list[i], c)]

        # remove piles that we no longer need; any pile that won't
        # fit larger items (multiple items can have the same size)
        del piles[target - size + 1:]

该解决方案恰好使用了itertools.repeat()，但这只是因为可以方便地从麻袋中的计数器产生最终输出。

对于您的玩具示例，使用(value, size)与背包问题相同的典型格式，会产生：

>>> input_list = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6)]
>>> target_size = 4
>>> solution = unbounded_knapsack_combos(input_list, target_size)
>>> [[s for _, s in sack] for sack in solution]
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]

这只会生成实际可行的组合，仅此而已。

该功能与完整解决方案的不同之处在于，这里保留所有可能的组合，而不是仅保留对组合项目具有最佳价值的一种组合。而且因为我们正在生成所有组合，所以不需要像链接 DP 方法那样按项目的价值比率对项目进行排序（排序有助于避免在循环中复制太多次优解决方案）。

生成的递归版本schwobaseggl本质上做同样的事情；为给定的容量创建麻袋，递归调用为下一个更大的容量添加更多项目。我的恰好是迭代的，因此您不会遇到 Python 的递归限制，并且它会在找到结果时产生结果（就像itertools会那样）。递归版本还被迫重复连接列表（N == 递归深度的 O(N^2) 操作），因此迭代方法要快得多。