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

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

拆卸：

^{pr2}$

是输出

input_list

是以下形式的元组列表（[…]，number_of_packages）

target_number_of_packages

是我需要到达的包裹数量。我可以任意组合“input_list”列表中的任意多个元素（允许重复），但在添加“number_of_packages”时，需要精确地达到目标_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.总和（comb）=目标放入itertools.combinations_与_替换-如果可能的话。在

我改变了问题，因为我用不同的方式解决了潜在的问题，但其中的一部分还是我想知道的。既然没有答案，我认为编辑是恰当的。

Answer 1

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

从评论来看，你似乎在问如何使用回调函数来解决问题，但我认为你还不完全了解问题空间，也不知道list.sort(key=...)是如何工作的。Python的sort实现显式地调用key回调，根据选择，被调用的函数传递信息，sort函数根据返回的内容改变行为；key函数不能选择返回值的结果。在

在我看来，你问错了问题。在

您试图解决的问题是Knapsack Problem的子集；您有一个无界的变量，因为我可以根据需要组合列表“input_list”的任意多个元素（允许重复）。在

试图用itertools来解决它是错误的方法；itertools函数将生成许多不正确的组合。实际上，您是在为输出大小1到目标大小生成重复（multisets）的所有组合，因此您可以为每个给定大小生成calculate the number of such 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组合浪费每个可行的输出！随着输入大小的增大，这个比率只会变得（非常）糟糕。在

全背包问题通常用dynamic programming approach来解决。编程chrestomathy网站Rossettacode.org网站有一个great example in Python on how to use DP for an unbounded knapsack solution。基本上，您为每个级别的容量（从零到最大）保留一个“sacks”表，并保持该表的更新，以查看将当前项添加到具有该项空间的sack中是否会产生比该sack的最佳组合更好（更有价值）的sack。在

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

从DP解决方案中抽出一片叶子，迭代解决方案将使用一系列堆的麻袋，并将这些麻袋复制到下一堆，因为您向每个有空间的袋子中添加更多这样的项目：

^{pr2}$

这个解决方案恰好使用itertools.repeat()，但这只是因为它便于从sack中的计数器生成最终输出。在

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

^{3}$

这只会产生实际可行的组合，而不会产生更多。在

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

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

Answer 2

生成所有可能的组合并用匹配的和过滤掉这些组合的工作太多了。但是，您可以编写自己的函数，精确且仅生成所需的函数：

def combos(lst, total, max=None):
    if total < 0:
        return
    elif total == 0:
        yield []
    for x in lst:
        if max is None or x <= max:
            for com in combos(lst, total - x, x):
                yield [x] + com

>>> list(combos([1, 2, 3, 4, 5, 6], 4))
[[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]]

Answer 3

使用itertools.combinations_与_替换生成一个类似的列表

from itertools import combinations_with_replacement

input_list = [1,2,3,4,5,6] 

l = [list(combination_with_replacement(input_list, i)) for i in range(5)]
res = [list(filter(lambda x: sum(x) == 4, i)) for i in l]
# [[], [(4,)], [(1, 3), (2, 2)], [(1, 1, 2)], [(1, 1, 1, 1)]]