CODEWITHSUNDEEP
pythonlistrecursiondata-partitioning
Tony Kaitong Chen
Tony Kaitong Chen

Reputation: 21

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.

Upvotes: 2

Views: 8038

Answers (3)

user13094861
user13094861

Reputation:

Wolfram Mathworld:

P(n, k) denotes 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. (Note that if "exactly k" is changed to "k or fewer" and "largest is exactly k," is changed to "no element greater than k," then the partition function q is obtained.) For example, P(5, 3) = 2, since the partitions of 5 of length 3 are {3, 1, 1} and {2, 2, 1}, and the partitions of 5 with maximum element 3 are {3, 2} and {3, 1, 1}.
...
P(n, k) can be computed from the recurrence relation P(n, k) = P(n-1, k-1) + P(n-k, k) (Skiena 1990, p. 58; Ruskey) with P(n, k) = 0 for k > n, P(n, n) = 1, and P(n, 0) = 0.

So if we want to calculate the number of ways of writing n as a sum, we should calculate-

enter image description here

Let's define 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)

Now we can calculate the number of ways of writing n as a sum:

n = 6
partitions_count = 0

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

print(partitions_count)

# Output:
# 11

As p(n, k) is a recursive function, you can boost the speed by saving values of each p(n, k) in a dictionary (thanks to the fast hash-based search!) and check if we have calculated the value (check if the value is in the dictionary) before calculating:

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

Full function:

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

Helpful links:

Upvotes: 1

Jan
Jan

Reputation: 23

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

Upvotes: -2

agf
agf

Reputation: 177000

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.

Upvotes: 4

Related Questions