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