# Recursive integer partitions in C

Here is a recursive algorithm to generate integer partitions in antilexicographic order. The function partitions() takes an integer to partition, and a callback function to call for each partition found.

#include <stdlib.h>

unsigned int min(int a, int b)
{
return a < b ? a : b;
}

typedef void (*partitionfn)(const unsigned int *, size_t);

static void partitions_recursive(unsigned int n, unsigned int maximum, unsigned int *partition,
size_t length, partitionfn fun)
{
unsigned int i;
if (n == 0) {
fun(partition, length);
}
for (i = min(maximum, n); i >= 1; i--) {
partition[length] = i;
partitions_recursive(n - i, i, partition, length + 1, fun);
}
}

void partitions(unsigned int n, partitionfn fun)
{
unsigned int *partition = malloc(n * sizeof(unsigned int));
if (partition) {
partitions_recursive(n, n, partition, 0, fun);
free(partition);
}
}


An example program:

#include <stdio.h>

void print(const unsigned int *partition, size_t length)
{
unsigned int i;
for (i = 0; i < length; i++) {
printf("%u ", partition[i]);
}
putchar('\n');
}

int main(void)
{
partitions(6, print);
return 0;
}


The output:

6
5 1
4 2
4 1 1
3 3
3 2 1
3 1 1 1
2 2 2
2 2 1 1
2 1 1 1 1
1 1 1 1 1 1


Reference: Partition.java