A single, parameterized, algorithm solves two different enumeration problems: number partitions and k sized subsets of multisets.

combined_algorithm.py

# combined_algorithm.py
# A single, parameterized, algorithm solves two different enumeration problems: number partitions and k sized subsets of multisets. 

def fill_from_right(k, array, capacities, get_value):
    for i in range(len(array)):
        assert (array[i] == 0)
        while array[i] < capacities[i] and k > 0:
            array[i] += 1
            k -= get_value(i)
        if k == 0:
            break
    return array


def fill_from_left(k, array, capacities, get_value):
    return fill_from_right(k, array[::-1], capacities[::-1], lambda i: get_value(len(array) - i - 1))[::-1]


def combined(n, k, capacities, get_value):
    array = fill_from_right(k, [0] * n, capacities, get_value)
    filled_from_left = fill_from_left(k, [0] * len(array), capacities, get_value)
    while array != filled_from_left:
        yield array[:]
        value_sum = 0  # sum of value of buckets at indices <= i
        for i in range(n):
            if array[i] > 0:
                bits = array[i]
                array[i] = 0
                value = get_value(i) * bits
                value_sum += value
                if value_sum >= get_value(i + 1) and array[i + 1] != capacities[i + 1]:
                    array[i + 1] += 1
                    fill_from_right(value_sum - get_value(i + 1), array, capacities, get_value)
                    break
    yield array[:]


def number_partitions(n):
    return combined(n, n, [n] * n, lambda i: 1 + i)


def subsets(n, k):
    return combined(n, k, [1] * n, lambda i: 1)


def multisets(n, k, multiplicities):
    return combined(n, k, multiplicities, lambda i: 1)


# for x in list(number_partitions(7)): print(x)
# for x in list(subsets(6, 2)): print(x)
for x in list(multisets(3, 4, [3] * 5)): print(x)