Can pythons lambda be used to change the inner working of another function?

Question

I have the following code snippet which i needed to (massively) speed up. As is, it's hugely inefficient.

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

Disassembled:

possible_combos 

is the output

input_list

is a list of tuples in the form ([...],number_of_packages)

target_number_of_packages

is the number of packages I need to reach. I can combine as many elements of the list "input_list" as I want (repetitions are allowed), but need to reach exactly target_number_of_packages when adding their "number_of_packages", else the combination is not valid.

I was thinking about something like

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

but wasn't able to fill the blank.

My question is, is it at all possible to use lambda this way? I don't need an answer for how to deal with this specific usecase because I've solved it differently (with itertools product an a recursive generator function), but I'd still like to know, would there have been a solution?

In short: Is it possible to use lambda to change a value inside another function on the fly?

Minimal example for the problem:

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

And I'm looking for something roughly equivalent to, but faster than,

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

Just with the np.sum(comb)==target put in the itertools.combinations_with_replacement - if possible at all.

I've changed the question because I solved the underlying problem differently, but part of it is still something I'd like to know about. As there where no answers, I think an edit is apropriate.

Answer 1

lambda is just syntax, allowing you to create a function object in an expression (def functionname(..): ... is a statement, and you can't use statements inside an expression). So a lambda just creates a function object, and is nothing special. You can't use functions to alter the local namespace of another function at runtime, no.

From comments it is appears you are asking about how you could use a callback to perhaps solve your problem, but I don't think you fully understand your problem space yet nor how things like list.sort(key=...) work. Python's sort implementation explicitly calls the key callback, by choice, the function called is passed information and the sort function alters behaviour based on what is returned; the key function doesn't get to choose what happens with the returned value.

You are asking the wrong question here, in my opinion.

The problem you are trying to solve a subset of the Knapsack Problem; you have the unbounded variant, as I can combine as many elements of the list "input_list" as I want (repetitions are allowed).

Trying to use itertools to solve it is the wrong approach; itertools functions will generate to many incorrect combinations. You are essentially generating all combinations with repetition (multisets) for output sizes 1 through target size, so you can calculate the number of such multisets for each given size, and summing them:

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

For your toy example, with 6 inputs and a target size of 4, you are generating 209 different combinations, but there are only 5 viable combinations. That's a whopping 40.8 combinations wasted per viable output! With larger input sizes this ratio is only going to get (much) worse.

The full knapsack problem is commonly solved using a dynamic programming approach. The programming chrestomathy site Rossettacode.org has a great example in Python on how to use DP for an unbounded knapsack solution. Basically, you keep a table of 'sacks' for every level of capacity (from zero to max) and keep that table updated as you see if adding the current item to sacks that have space for the item produces a better (more valuable) sack than the best combination for that sack, so far.

But when producing all possible combinations, you are better of with your own iterative or recursive approach. There is no ready-made itertools function you can use here, nor would using a callback function make this any easier.

Taking a leaf out of the DP solution, an iterative solution would use a series piles of sacks for each possible capacity total, and copy these up to the next pile as you add more such items to each sack that has space for them:

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

This solution happens to use itertools.repeat(), but only because it is convenient to produce the final output from the counters in the sacks.

For your toy example, using the same (value, size) format typical of the knapsack problem, this produces:

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

This only ever generates the actual viable combinations, and nothing more.

The function differs from the full solution in that here all possible combinations are kept, rather than only the one combination with the best value for the items combined. And because we are generating all combinations, there is no need to sort the items by their value ratio, as the linked DP approach does (the sorting helps avoid copying too many less optimal solutions in the loop).

The recursive version schwobaseggl produced essentially does the same thing; create sacks for a given capacity, and the recursive calls add more items for the next larger capacity. Mine just happens to be iterative so you won't run into Python's recursion limits, and it yields results as it finds them (like itertools would). The recursive version also is forced to repeatedly concatenate lists (a O(N^2) operation for N == recursion depth), so the iterative approach is a lot faster.

Answer 2

Generating all possible combinations and filtering out the ones with the matching sum does way too much work. But you can write your own function that generates exactly and only the ones you need:

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