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

一尘不染

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

python

（重新发布，因为我没有对之前的帖子做出任何回应）
我试图编写一个Python代码以将数字为’n’的弱整数组合（分区）转换为’k’部分，但要使用MINIMUM和MAXIMUM每个分区上的值约束（请参见下面的示例）。同样，必须按字典顺序生成分区。我发现了一些相关的帖子，但无法实现。任何帮助将不胜感激。

范例：
n = 5的整数分割区（k = 3）：
[5,0,0]，[4,1,0]，[4,0,1]，[3,2,0]，[3， 1,1]，[3,0,2]，…，[0,0,5]
在对分区中的每个整数施加MINIMUM值0和MAXIMUM值3的约束之后，我应该得到：
[ 3,2,0]，[3,1,1]，[3,0,2]，…依此类推。

阅读 350

2021-01-20

共1个答案

一尘不染

使用递归生成器函数最容易解决此类问题。要生成n分成k几部分的分区，我们可以选择第一个part 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)

2021-01-20