Number of ways to partition a number in Python

问题:

I have defined a recursive function that takes a number, n, and returns a list of lists of the numbers that sum to that number (partitions):

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

I was wondering how to make the function return the number of partitions for number n.

For example, P(6) would return 10.

回答1:

If you look at the "Partition function formulas" section of the Partiton (number theory) page on Wikipedia, you'll see that there isn't a simple way to find the partition number.

Instead, your best bet is probably:

sum(1 for _ in P(6))

or, slightly simpler but memory hogging for large numbers

len(list(P(6)))

using your existing function.

Also note if you want to be able to save the values returned by P, you should be yielding p[:] not p -- you want to make a copy, not yield the same list (which you change) over and over. You can see why if you do list(P(6)) -- it returns a list of the same empty list repeated over and over.

Fore more info about partitioning, see Partitioning with Python.

回答2:

Here's an example in Java for computing your desired result.

/**
 * 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;
}