用Python分割一个数的方法数

Question

我定义了一个递归函数，这个函数接收一个数字 n，然后返回一个包含多个列表的列表，这些列表里的数字加起来正好等于这个数字（我们称之为“分区”）。

def P(n):
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return

    for p in P(n-1):        
        p.append(1)
        yield p
        p.pop()
        if p and (len(p) < 2 or p[-2] > p[-1]):
            p[-1] += 1
            yield p

我在想，怎么才能让这个函数返回数字 n 的“分区”数量呢？

举个例子，P(6) 应该返回 10。

Answer 1

这里有一个Java的例子，可以用来计算你想要的结果。

/**
 * Returns the number of ways the number n can be partitioned
 * into sums of positive integers larger than k. 
 * @param k
 * @param n
 * @return
 */
public static long partition(long k, long n){
    long sum = 0;
    if(k > n) return 0;
    if(k == n) return 1;
    sum += partition(k+1, n) + partition(k, n-k);
    return sum;
}

Answer 2

Wolfram Mathworld:

P(n, k)表示将数字n写成恰好k个加数的方式数，或者说是将n分成的部分中，最大的一部分正好是k的方式数。（注意，如果把“恰好k”改成“k个或更少”，把“最大是k”改成“没有部分大于k”，就会得到另一个叫做q的分区函数。）举个例子，P(5, 3) = 2，因为5可以用3个数分成的方式有{3, 1, 1}和{2, 2, 1}，而5中最大元素为3的分法有{3, 2}和{3, 1, 1}。
...
P(n, k)可以通过递推关系来计算： P(n, k) = P(n-1, k-1) + P(n-k, k) （Skiena 1990, 第58页；Ruskey）并且有P(n, k) = 0 当 k > n，P(n, n) = 1，和 P(n, 0) = 0。

所以如果我们想计算将n写成和的方式数，我们应该计算-

我们来定义P(n, k)：

def p(n, k):
    """Gives the number of ways of writing n as a sum of exactly k terms or, equivalently, 
    the number of partitions into parts of which the largest is exactly k.  
    """
    if n < k:
        return 0
    if n == k:
        return 1
    if k == 0:
        return 0

    return p(n-1, k-1) + p(n-k, k)

现在我们可以计算将n写成和的方式数：

n = 6
partitions_count = 0

for k in range(n + 1):
    partitions_count += p(n, k)

print(partitions_count)

# Output:
# 11

由于p(n, k)是一个递归函数，你可以通过把每个p(n, k)的值保存在一个字典中来提高速度（感谢快速的哈希查找！），在计算之前先检查一下这个值是否已经计算过（检查这个值是否在字典中）：

dic = {}
def p(n, k):
    """Gives the number of ways of writing n as a sum of exactly k terms or, equivalently, 
        the number of partitions into parts of which the largest is exactly k.  
    """
    if n < k:
        return 0
    if n == k:
        return 1
    if k == 0:
        return 0

    key = str(n) + ',' + str(k)
    try:
        temp = dic[key]
    except:
        temp = p(n-1, k-1) + p(n-k, k)
        dic[key] = temp
    finally:
        return temp

完整函数：

def partitions_count(n):
    """Gives the number of ways of writing the integer n as a sum of positive integers,
    where the order of addends is not considered significant.
    """
    dic = {}
    def p(n, k):
        """Gives the number of ways of writing n as a sum of exactly k terms or, equivalently, 
        the number of partitions into parts of which the largest is exactly k.  
        """
        if n < k:
            return 0
        if n == k:
            return 1
        if k == 0:
            return 0
        
        key = str(n) + ',' + str(k)
        try:
            temp = dic[key]
        except:
            temp = p(n-1, k-1) + p(n-k, k)
            dic[key] = temp
        finally:
            return temp
    
    partitions_count = 0
    for k in range(n + 1):
        partitions_count += p(n, k)
    return partitions_count

有用的链接：

• 分区 - Numberphile
• 分区（数论）

Answer 3

如果你去维基百科的分区（数论）页面，看看“分区函数公式”这一部分，你会发现没有一个简单的方法来找到分区数。

所以，你最好的选择可能是：

sum(1 for _ in P(6))

或者，稍微简单一点，但对于大数字来说会占用很多内存：

len(list(P(6)))

使用你现有的函数。

另外，如果你想保存P返回的值，你应该使用yield p[:]，而不是p。因为你想要的是一个副本，而不是重复使用同一个（你会改变的）列表。如果你执行list(P(6))，你会发现它返回的是同一个空列表重复出现。

想了解更多关于分区的信息，可以查看用Python进行分区。