得到精确的k个部分。递归和分区算法p(n，k)
得到精确的k个部分。递归和分区算法p(n，k)
提问于 2015-04-16 18:33:18
我想列举k个部分中n的所有分区。
对于p(5,3)，我得到了k=3 => (3,1,1)，(2,2,1)的2个分区。
下面是我在搜索和查看堆栈溢出时所发现的：
def p(n,k):
lst = []
if n < k:
return lst
elif k == 1:
return lst
elif k == n:
return lst
else:
p(n-1, k-1)
p(n-k, k)
return lst^这是我想要的表格，
实际上，找到k个部分的和很容易，您可以返回p(n-1，k-1) +p(n，k)。至于我，我需要列出这样的元素(3,1,1)，(2,2,1)。
我的主要问题是递归地“构建”这些分区。你会怎么处理这个？
编辑
如果你得到基例k= 1，加+ 1，k-1次。(4,1)然后(4,1,1)
如果你得到的基例k= n，分裂并移除一个到每个部分。
类似：(3,3)然后(3,3,3)然后(2,2,2)
如果你得到根号k< n，什么都没有
基本上，我的问题是“堆叠”从大小写到顶部，得到一个完整的列表p(6,3) = (2,2,2)，(4,1,1)，(3,2,1)。
回答 1
Stack Overflow用户
发布于 2015-04-16 21:04:50
我将向递归函数添加第三个参数m，这是元素在分区中可以拥有的最大值。然后，我会像这样定义函数：
def p(n, k, m=None):
if m is None:
m = n - k + 1 # maximum can be n - k + 1 since minimum is 1
if k == 0:
if n == 0:
yield ()
return
for i in xrange(1, m + 1): # first could be from 1 to the maximum
# the rest of the sum will be n - i among k - 1 elements with
# maximum i
for t in p(n - i, k - 1, i):
yield (i, ) + t示例：
>>> list(p(10, 3))
[(4, 3, 3), (4, 4, 2), (5, 3, 2), (5, 4, 1), (6, 2, 2), (6, 3, 1), (7, 2, 1), (8 , 1, 1)]
>>> list(p(6, 2))
[(3, 3), (4, 2), (5, 1)]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29683202
复制相关文章
相似问题
腾讯云开发者
