# Partition function using dynamic programming in C

A partition of an integer is a way of writing it as a sum of positive integers. For example, partitions of 5 are:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

The order of numbers in a partition doesn’t matter. The number of partitions of a number $$n$$ is given by the partition function $$p(n)$$.

The first few values of $$p(n)$$ are 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, … (A000041).

The partition function can be computed using a dynamic programming table-filling algorithm. Here it is in C:

#include <stdlib.h>

unsigned int partition(unsigned int n)
{
unsigned int i, j;
unsigned int result;
unsigned int **table;

if (n == 0) {
return 1;
}

table = malloc((n + 1) * sizeof(unsigned int *));
for (i = 0; i <= n; i++) {
table[i] = malloc((n + 1) * sizeof(unsigned int));
}

for (i = 0;i <= n; i++) {
table[i][0]=0;
}
for (i = 1; i <= n; i++) {
table[0][i] = 1;
}

for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (j > i) {
table[i][j] = table[i][j - 1];
}
else {
table[i][j] = table[i][j - 1] + table[i - j][j];
}
}
}

result = table[n][n];
for (i = 0; i <= n; i++) {
free(table[i]);
}
free(table);

return result;
}


Example program:

#include <stdio.h>

int main(void)
{
unsigned int i;
for (i = 0; i < 31; i++) {
printf("%d\n",partition(i));
}

return 0;
}


Output:

1
1
2
3
5
7
11
15
22
30
42
56
77
101
135
176
231
297
385
490
627
792
1002
1255
1575
1958
2436
3010
3718
4565
5604