python - 在 Python 中将整数 n 生成受限弱整数组合(或分区)为 k 部分

Question

(重新发帖，因为我之前的帖子没有得到任何回复)
我正在尝试编写一个Python代码来生成数字“n”到“k”部分的弱整数组合(分区)，但每个分区都有最小值和最大值约束(请参见下面给出的示例)。此外，分区必须按字典顺序生成。我找到了一些相关的帖子，但未能实现。任何帮助将不胜感激。

示例:
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]、...等等。

相关帖子:
Elegant Python code for Integer Partitioning
Generate lexicographic series efficiently in Python

Answer 1

使用递归生成器函数可以最直接地解决此类问题。要将n划分为k部分，我们可以选择第一部分v，然后递归划分n - v code> 分成 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)