python - 递归生成所有位数和为 n 的 k 位数字

Question

我正在解决一个问题，我正在寻找所有 k 位数字，其数字总和为给定的 n。

我找到了如何做到这一点并将其作为整数分区问题来处理，但是我希望只能输入 n 和 k 数字(没有 max_element)但是当我尝试从代码中删除它时它不会似乎不再起作用了。

我怎样才能改变它并反转它？

def c(n, k, max_element):
    allowed = range(max_element, 0, -1)

    def helper(n, k, t):
        if k == 0:
            if n == 0:
                yield t
        elif k == 1:
            if n in allowed:
                yield t + (n,)
        elif 1 * k <= n <= max_element * k:
            for v in allowed:
                yield from helper(n - v, k - 1, t + (v,))
    return helper(n, k, ())

for p in c(5, 3, 3):
    print(p)

我尝试使用相反的方法，但显然它在生成器中不起作用。

结果:

(3, 1, 1)
(2, 2, 1)
(2, 1, 2)
(1, 3, 1)
(1, 2, 2)
(1, 1, 3)

预期结果:

113 122 131 212 221 311

Answer 1

这里有几个问题；第一个是你想要按顺序排列数字，而这段代码以相反的顺序生成它们，因为 range(max_element, 0, -1) .另一个问题是，由于您要生成数字，因此最小元素应为 0，最大元素应始终为 9。我们可以通过将该范围更改为 range(10) 来解决这两个问题。 .

我们仍然需要注意不要生成以 0 开头的数字，所以我们将 allowed一个参数并使用 range(1, 10)只是第一个数字。我还更改了它以将结果作为整数而不是元组返回。

供引用，此生成器函数的代码来自my answer to another question .

def c(n, k):
    def helper(n, k, t, allowed):
        if k == 0:
            if n == 0:
                yield t
        elif k == 1:
            if n in allowed:
                yield 10*t + n
        elif 0 <= n <= 9 * k:
            for v in allowed:
                yield from helper(n - v, k - 1, 10*t + v, range(10))

    return helper(n, k, 0, range(1, 10))

例子:

>>> for p in c(5, 3):
...     print(p)
...
104
113
122
131
140
203
212
221
230
302
311
320
401
410
500