在Python中将整数n的受限弱整数组成部分(或分区)生成为k个部分 [英] Generate restricted weak integer compositions (or partitions) of an integer n into k parts in Python
问题描述
(重新发布,因为我对之前的帖子没有任何回复)
我正在尝试编写Python代码以将数字'n'的弱整数组成部分(分区)转换为'k'部分,但每个分区上都有MINIMUM和MAXIMUM值约束(请参见下面的示例).同样,必须按字典顺序生成分区.我发现了一些相关的帖子,但无法实现.任何帮助将不胜感激.
(Re-posting, as I did not get any response to my previous post)
I am trying to write a Python code to generate weak integer compositions (partitions) of a number 'n' into 'k' parts but with a MINIMUM and MAXIMUM value constraint on each partition (see example given below). Also, the partitions have to be generated in lexicographic order. I have found some related posts but have not been able to implement it. Any help will be appreciated.
示例:
在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]
在强加分区中的每个整数具有MINIMUM值0和MAXIMUM值3的约束之后,我应该得到:
仅限[3,2,0],[3,1,1],[3,0,2]等.
Example:
Possible integer partitions for n=5 in k=3 parts:
[5,0,0], [4,1,0], [4,0,1], [3,2,0], [3,1,1], [3,0,2], ..., [0,0,5]
After imposing the constraint that each integer in the partition has a MINIMUM value 0 and a MAXIMUM value 3, I should get:
[3,2,0], [3,1,1], [3,0,2], ...so on, only.
相关文章:
用于整数分区的优雅Python代码
在Python中高效地生成词典序列
Related posts:
Elegant Python code for Integer Partitioning
Generate lexicographic series efficiently in Python
推荐答案
使用递归生成器函数最容易解决此类问题.要将n
的分区生成为k
个部分,我们可以选择第一个部分v
,然后将n - v
递归地划分为k - 1
个部分.
This kind of problem is most straightforward to solve with a recursive generator function. To generate partitions of n
into k
parts, we can select the first part v
, and then recursively partition n - v
into k - 1
parts.
您希望早期的解决方案在第一位置具有更大的数字,因此我们将按降序选择v
.
You want earlier solutions to have larger numbers in the first position, so we'll choose v
in descending order.
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个部分的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!