What is an algorithm to generate every solution to x1 x2 ....xk = n, xi >= 0? I am aware it is some form of backtracking but I am not sure how to implement this.

CodePudding user response：

Without recursion, quicky modified from my answer with non-zero partitions, implements stars and bars principle

from itertools import combinations

#print(parts(7,4))

def partswithzeros(n,r):
    result = []
    for comb in combinations(range(n r-1), r-1):
        zpart = [comb[0]]   [comb[i]-comb[i-1]-1 for i in range(1,r-1)]   [n r-2 - comb[-1]]
        result.append(zpart)
    return(result)

print(partswithzeros(5,3))

>>>[[0, 0, 5], [0, 1, 4], [0, 2, 3], [0, 3, 2], [0, 4, 1], [0, 5, 0], [1, 0, 4],
    [1, 1, 3], [1, 2, 2], [1, 3, 1], [1, 4, 0], [2, 0, 3], [2, 1, 2], [2, 2, 1],
    [2, 3, 0], [3, 0, 2], [3, 1, 1], [3, 2, 0], [4, 0, 1], [4, 1, 0], [5, 0, 0]]

CodePudding user response：

Straightforward recursion will work here. The first element of the solution can take any value x_i from 0 to n. To find the second and subsequent values, find the possible partitions for (n−x_i, k−1). The recursion stops when k=1, in which case the final element must be equal to the remaining value of n.

I hope that makes sense. Perhaps the following Python code will help:

def get_partitions(n, k, p=[]):
    # End point. If k=1, then the last element must equal n
    # p[] starts as an empty list; we will append values to it
    # at each recursive step
    if k <= 1:
        if k == 1 and n >= 0:
            yield(p   [n])
        return
        # If k is zero, then there is no solution
        yield None
    # Recursively loop over every possible value for the current element
    for i in range(0,n 1):
        yield from get_partitions(n-i, k-1, p [i])

>>> for p in get_partitions(4,3):
...     print(p)
... 
[0, 0, 4]
[0, 1, 3]
[0, 2, 2]
[0, 3, 1]
[0, 4, 0]
[1, 0, 3]
[1, 1, 2]
[1, 2, 1]
[1, 3, 0]
[2, 0, 2]
[2, 1, 1]
[2, 2, 0]
[3, 0, 1]
[3, 1, 0]
[4, 0, 0]