2

我定义了一个递归函数，它接受一个数字 ,n并返回list与该数字相加的数字列表（分区）：

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

我想知道如何让函数返回number的分区数n。

例如，P(6)将返回10.

4

3 回答 3

4

如果您查看 Wikipedia 上Partiton（数论）页面的“分区函数公式”部分，您会发现没有一种简单的方法可以找到分区号。

相反，您最好的选择可能是：

sum(1 for _ in P(6))

或者，稍微简单一点，但会占用大量内存

len(list(P(6)))

使用您现有的功能。

另请注意，如果您希望能够保存由返回的值，您不P应该这样做——您想要制作副本，而不是一遍又一遍地产生相同的列表（您更改的列表）。如果你这样做了，你就会明白为什么——它会返回一个重复的相同空列表的列表。yieldp[:]plist(P(6))

有关分区的更多信息，请参阅使用 Python 进行分区。

于 2011-10-18T04:15:03.810 回答
0

Wolfram 数学世界：

P(n, k) 表示将 n 写为恰好 k 项之和的方式的数量，或者等价地，表示划分为其中最大恰好为 k 的部分的数量。（注意，如果“exactly k”改成“k or less”，“largest is just k”改成“no element大于k”，则得到配分函数q。）例如，P(5 , 3) = 2，因为长度为 3 的 5 的分区是 {3, 1, 1} 和 {2, 2, 1}，最大元素为 3 的 5 的分区是 {3, 2} 和​​ {3， 1, 1}。
...
P(n, k) 可以从递归关系中计算出来 P(n, k) = P(n-1, k-1) + P(nk, k) (Skiena 1990, p. 58; Ruskey)对于k > n，P(n, k) = 0，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

有用的网址：

于 2020-09-04T09:48:22.353 回答
-2

这是用于计算所需结果的 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;
}
于 2012-08-03T21:19:45.620 回答