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 回答