在Python中将整数n的受限弱整数组合(或分区)生成为k个部分
(重新发布,因为我没有对之前的帖子做出任何回应)
我试图编写一个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],…依此类推。
回答:
使用递归生成器函数最容易解决此类问题。要生成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)
以上是 在Python中将整数n的受限弱整数组合(或分区)生成为k个部分 的全部内容, 来源链接: utcz.com/qa/399012.html