总和的递归实现目标 Python

Question

我有以下方法，给定一个目标整数，生成从有序的整数行创建该整数的所有方法，条件是列索引（从一个开始）乘以数字总和每行的目标。

下面是实现此目的的一些代码。

target = 7
for x in range(math.floor(target/4)+1):
    for f in range(math.floor((target-4)/3)+1):
        for t in range(math.floor((target-4*x-3*f)/2)+1):
            s = target - 2*t - 3*f - 4*x
            print(s,t,f,x)

7 0 0 0
5 1 0 0
3 2 0 0
1 3 0 0
4 0 1 0
2 1 1 0
0 2 1 0
3 0 0 1
1 1 0 1
0 0 1 1

请注意，所有行的总和为 target=7，即取最下面的行 0*1 + 0*2 + 1*3 + 1*4=7。

在一般情况下，我不知道我需要多少列。例如，我可能只是

target = 7
for t in range(math.floor(target/2)+1):
    s = target - 2*t
    print(s,t)

或者实际上，还有更多 for 循环。

我如何概括这一点，最有可能基于递归解决方案，以便列数成为参数？

Answer 1

这是一个递归的解决方案。您只需运行通过最后一列的选项，然后使用剩余的列获取剩余的组合。

def gencombos( target, column ):
    if column == 1:
        yield [target]
    else:
        for i in range( 0, target//column+1 ):
            for row in gencombos( target-i*column, column-1 ):
                yield row+[i]

for row in gencombos( 7, 4 ):
    print(row)

输出：

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

您可以将其更改为对 (7,6) 的调用以查看差异。

总和的递归实现目标 Python

recursive implementation of sum to target Python

python

recursion

combinations

combinatorics