Partitions

For a positive integer n, the partitions of n are all the possible different ways of writing n as the sum of positive integers.

For example, these are the possible partitions (7) for $n = 5$:

partitions(5):  
5 = 1 + 1 + 1 + 1 + 1  
5 = 1 + 1 + 1 + 2  
5 = 1 + 1 + 3  
5 = 1 + 2 + 2  
5 = 1 + 4  
5 = 2 + 3  
5 = 5  

We don’t consider the particular order of the addends. That means that for us $5 = 2 + 3$ is the same partition of $5 = 3 + 2$.

The problem

Given a positive integer $n$, compute all the partitions of $n$.

The solution

This is a scala code snippet that solves the problem:

def partitions(n: Int): List[List[Int]] = partitions(n, 1)

def partitions(n: Int, m: Int): List[List[Int]] =  
    n match {
        case _ if m > n => List()
        case _ if m == n => List(List(n))
        case _ if m < n =>
            val ns1 = partitions(n - m, m).map { m :: _ }
            val ns2 = partitions(n, m + 1)
            ns1 ::: ns2
    }

Discussion

The solution is using a recursive description of what a partition is.

Looking back at our initial example for partitions of 5, we can easily guess the recursive structure of the list. 

Take for example the partitions starting with 1. If we remove the leading 1, we have all the partitions for 4. For those starting with 2 , the remaining part is a partition of 3, and so on.

In general, if a partition of $n$ is starting with $k$, then the remaining addends form a partition of $n-k$.

In pseudo-code we can express this relation in the following way:

partitions(5) =  
1 + partitions(4)  
2 + partitions(3)  
3 + partitions(2)  
4 + partitions(1)  
5 + partitions(0)  

where with k + partitions(m) we mean the set of all the partitions of $k + m$ whose first addend is $k$ and the remaining addends form a partition of $m$.

There is one problem in this approach though, and it is that the same partition can occur multiple times. For example 

5 = 1 + 2 + 2 // This belongs to 1 + partitions(4)  
5 = 2 + 1 + 2 // This belongs to 2 + partitions(3)  

This is a common problem in defining recursive algorithms that enumerate all the elements of a set: often the first recursive algorithm that comes to our mind does not guarantee unicity, and an extra step (or a different data structure, like a Set in our case) is necessary.

Let's now look how to achieve unicity without the need of an extra step.

1 + partitions(4) contains all the partitions with at least one 1. We can even say more: it is exactly that set, because obviously each partition in 1 + partitions(4) contains at least one 1.

To avoid repetitions, it is enough to consider, at the second step, the partitions of $3$ that do not contain any $1$.

partitions(5) =  
1 + partitions(4, 1)  
2 + partitions(4, 2)  
...

where partitions(n, k) denotes the set of partitions of the number $n$ whose addends are greater or equal than $k$.

For example, partitions(4, 2) is formed only by the partitions $4 = 2 + 2$ and $4 = 4$, since any other partition of $4$ contains at least one $1$.

At that point, for the same argument, we will already have all the partitions that contain either a $1$ or a $2$, and we can complete our example:

partitions(5) =  
1 + partitions(4, 1)  
2 + partitions(3, 2)  
3 + partitions(2, 3)  
4 + partitions(1, 4)  
5 + partitions(0, 5)  

It's then enough to solve the following

Problem 2

Given non-negative integers $n$ and $k$, compute all the partitions of $n$ composed by numbers greater or equal than $k$.

Base case

If $k > n$, clearly there are no such partitions. Therefore

partitions(n, k) = 0 if k > n  

If $k = n$ there is only one.

partitions(n, k) = 1 if k = n  

Inductive case

If $k < n$, we have two ways of building partitions of $n$ with elements greater or equal than $k$:
1. Partitions that contain $k$
2. Partitions that do not contain $k$

For case 1) we can take $k$ followed by all partitions of $n - k$ with numbers greater or equal than $k$. For the second case we take instead all the partitions of $n$ with numbers greater or equal than $k + 1$.

partitions(n, k) = partitions(n - k, k) + partitions(n, k + 1) if k > n  

The algorithm always terminates because at each step the difference $n - k$ strictly decreases, so at some point we will reach the base case $n - k <= 0$.

We can put everything together and get our original scala snippet:

def partitions(n: Int): List[List[Int]] = partitions(n, 1)

def partitions(n: Int, m: Int): List[List[Int]] =  
    n match {
        case _ if m > n => List()
        case _ if m == n => List(List(n))
        case _ if m < n =>
            val ns1 = partitions(n - m, m).map { m :: _ }
            val ns2 = partitions(n, m + 1)
            ns1 ::: ns2
    }

Follow ups

Compute only the number of partitions

If we just need to know the number of partitions of $n$, and not the full list of partitions, we can slightly modify the code to achieve that:

def numberOfPartitions(n: Int): Int = numberOfPartitions(n, 1)

def numberOfPartitions(n: Int, m: Int): Int =  
    n match {
        case _ if m > n => 0
        case _ if m == n => 1
        case _ if m < n =>
            numberOfPartitions(n - m, m) + numberOfPartitions(n, m + 1)
    }

As we can see from the asymptotic formula for numberOfPartitions(n) below, the function grows pretty quickly. These are the values for $n <= 49$ (the values are taken from the wonderful encyclopedia of integer sequences):

partitions(0)  = 1  
partitions(1)  = 1  
partitions(2)  = 2  
partitions(3)  = 3  
partitions(4)  = 5  
partitions(5)  = 7  
partitions(6)  = 11  
partitions(7)  = 15  
partitions(8)  = 22  
partitions(9)  = 30  
partitions(10) = 42  
partitions(11) = 56  
partitions(12) = 77  
partitions(13) = 101  
partitions(14) = 135  
partitions(15) = 176  
partitions(16) = 231  
partitions(17) = 297  
partitions(18) = 385  
partitions(19) = 490  
partitions(20) = 627  
partitions(21) = 792  
partitions(22) = 1002  
partitions(23) = 1255  
partitions(24) = 1575  
partitions(25) = 1958  
partitions(26) = 2436  
partitions(27) = 3010  
partitions(28) = 3718  
partitions(29) = 4565  
partitions(30) = 5604  
partitions(31) = 6842  
partitions(32) = 8349  
partitions(33) = 10143  
partitions(34) = 12310  
partitions(35) = 14883  
partitions(36) = 17977  
partitions(37) = 21637  
partitions(38) = 26015  
partitions(39) = 31185  
partitions(40) = 37338  
partitions(41) = 44583  
partitions(42) = 53174  
partitions(43) = 63261  
partitions(44) = 75175  
partitions(45) = 89134  
partitions(46) = 105558  
partitions(47) = 124754  
partitions(48) = 147273  
partitions(49) = 173525

Memoization

Caching intermediate values we can avoid a lot of recursive calls. For example, for $n = 49$ the algorithm is making $1836439$ calls. Of them $1834638$ can be avoided, having only $1801$ non-cached calls.

Time complexity

Since we are doing two recursive calls for each call, the algorithm is exponential in its non-memoized version, so it is no more than $O(2^n)$.

For the memoized version, since there are no more than $n^2$ distinct $(n, k)$ pairs that can feed the function numberOfPartitions, in that case the algorithm is $O(n^2)$.

An asymptotic formula

There is no known closed elementary formula known for numberOfPartitions(n), but Hardy and Ramanujan found, in 1918, its asymptotic behaviour:

$$ p(n) \sim \frac{1}{4 n{\sqrt{3}}} \exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right) $$

Further readings