1

（重新发布，因为我没有得到对我之前的帖子的任何回应）
我正在尝试编写一个 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], ...等等，只有。

相关文章：
用于整数分区的优雅 Python 代码
在 Python 中高效地生成字典序列

4

1 回答 1

2

使用递归生成器函数可以最直接地解决此类问题。要生成分块，我们可以选择第一个部分，然后递归地分n块。kvn - vk - 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)
于 2019-12-02T01:19:06.063 回答