[CODE] Integer partition function in Python (recursive and iterative)

Published on Thursday 15 December 2022

Tags: recursion2 iteration2 algorithm3 python7

[CODE] Integer partition function in Python (recursive and iterative)

The integer partition function p(n) is the number of ways of writing n as a sum of positive integers, where the order of the summands does not matter. Let's see how to implement it recurively and iteratively.

A partition of any integer n is a way to write n as a sum of other integers. The integer partition function partition(n) gives us the number of ways a positive integer n can be written as a sum of positive integers.

def partition(n):
    result = 0
    for k in range(n+1):
        result += p(n,k)
    return result

Now we can implement p(n,k), which yields the number of ways n can be written as a sum of k integers through a recursive or iterative function.

Recursive

def p(n,k):
    if n==0 and k==0: return 1
    if k <= 0 or n<=0: return 0
    return p(n-k,k)+p(n-1,k-1)

Iterative

def p(n,k):
    if n==0 and k==0: return 1
    if k <= 0 or n<=0: return 0
    return p(n-k,k)+p(n-1,k-1)