0

我希望在 k 部分中枚举 n 的所有分区。

所以对于 p(5,3) 我会得到 2 个 k = 3 => (3,1,1), (2,2,1) 的分区。

这是我通过搜索和查看 stackoverflow 发现的：

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(nk,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)]

在此处输入图像描述

4

1 回答 1

2

我会在递归函数中添加第三个参数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)]
于 2015-04-16T21:04:50.233 回答