将整数 n 生成受限的弱整数组合（或分区）到 Python 中的 k 个部分

Question

(重新posting，因为我之前的 post 没有收到任何回复)
我正在尝试编写一个 Python 代码来生成一个数字 'n' 的弱整数组合（分区）到 'k' 部分，但每个分区都有 MINIMUM 和 MAXIMUM 值约束（参见给出的示例以下）。此外，分区必须按字典顺序生成。我找到了一些相关的 posts 但一直无法实现。任何帮助将不胜感激。

示例：
在 k=3 个部分中 n=5 的可能整数分区：
[5,0,0], [4,1,0], [4,0,1], [3,2,0], [3,1,1], [3,0,2], .. ., [0,0,5]
施加分区中每个整数的最小值 0 和最大值 3 的约束后，我应该得到：
[3,2,0], [3,1,1], [3,0,2], ...等等，仅。

相关posts：
Elegant Python code for Integer Partitioning

Answer 1

这种问题用递归生成器函数解决最直接。要将 n 划分为 k 部分，我们可以 select 第一部分 v，然后递归地将 n - v 划分为 k - 1 部分。

您希望较早的解决方案在第一个位置具有较大的数字，因此我们将按降序选择 v。

def constrained_partitions(n, k, min_elem, max_elem):
    allowed = range(max_elem, min_elem-1, -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 min_elem * k <= n <= max_elem * k:
            for v in allowed:
                yield from helper(n - v, k - 1, t + (v,))

    return helper(n, k, ())

示例：

>>> for p in constrained_partitions(5, 3, 0, 3):
...     print(p)
... 
(3, 2, 0)
(3, 1, 1)
(3, 0, 2)
(2, 3, 0)
(2, 2, 1)
(2, 1, 2)
(2, 0, 3)
(1, 3, 1)
(1, 2, 2)
(1, 1, 3)
(0, 3, 2)
(0, 2, 3)

将整数 n 生成受限的弱整数组合（或分区）到 Python 中的 k 个部分

Generate restricted weak integer compositions (or partitions) of an integer n into k parts in Python

python

combinations

combinatorics

lexicographic

integer-partition