genpart.c

#include <stdio.h>

static void visit(const int a[], int n)
{
    int i;
    for (i = 0; i < n; ++i)
        printf("%d%c", a[i], (i == n-1) ? '\n' : ',');
}

// "Generating All Partitions: A Comparison Of Two Encodings", Kelleher & O'Sulllivan
// Algorithm 4.1
static void accel_asc(int a[], int n)
{
    int k = 1, y = n-1;

    a[0] = 0;
    while (k > 0) {
        int x = a[--k] + 1;
        while (2*x <= y) {
            a[k++] = x;
            y -= x;
        }
        while (x <= y) {
            a[k] = x++;
            a[k+1] = y--;
            visit(a, k+2);
        }
        y += x-1;
        a[k] = y + 1;
        visit(a, k+1);
    }
}

int main()
{
    int comb[10];
    accel_asc(comb, 5);

    return 0;
}