integer-partition.c

/** Enumerate integer partitions using Algorithm P from Knuth's TOACP V4 7.2.1.4

    $ cc -std=c99 *.c && echo 4 | ./a.out
    # Output:
    4
    3 + 1
    2 + 2
    2 + 1 + 1
    1 + 1 + 1 + 1
 */
#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIN(x, y) (((x) < (y)) ? (x) : (y))

typedef unsigned nonneg_t; /* represent non-negative integers */
#define NONNEG_MAX (nonneg_t)MIN(~((nonneg_t)0), LONG_MAX)
#define NONNEG_PRI "u"

static int read_long(FILE* stream, long* out);
static void generate_integer_partitions(size_t n, nonneg_t a[n],
					void (*visit)(size_t m, nonneg_t*));
static void print_integer_partition(size_t n, nonneg_t a[n]);


int main(void) {
  /* read natural number n >= 0 */
  long n;
  if (read_long(stdin, &n) < 0) { /* error */
    if (errno)
      perror("read_long");
    else
      fprintf(stderr, "read_long: failed to read number\n");
  }
  else if (n < 0 || n >= NONNEG_MAX) { /* out of range */
    fprintf(stderr, "number should be in [0, %" NONNEG_PRI ") range\n",
	    NONNEG_MAX);
  }
  else { /* print integer partitions */
    const size_t size = n + 1;
    nonneg_t a[size];
    generate_integer_partitions(size, a, print_integer_partition);
    return 0;
  }
  exit(EXIT_FAILURE);
}


/** Read line from stream and parse it as long int. Put it into `out` pointer.

    The line must contain a decimal number as recognized by strtol() and
    optionally leading and trailing whitespace. Everything else is an error.

    Return <0 on error; 0 on success. errno may be set for some errors.
 */
static int read_long(FILE* stream, long* out) {
  char str[BUFSIZ];
  char *s, *endptr = NULL;
  long val;
  errno = 0;
  if (out &&
      !(((s = fgets(str, BUFSIZ, stream)) == NULL || strlen(s) == (BUFSIZ-1)) ||
	((val = strtol(str, &endptr, 10)) == 0 && errno != 0) ||
	(errno == ERANGE && (val == LONG_MAX || val == LONG_MIN)) ||
	str == endptr)) {
    // `val` contains a number, check what left in the string
    while(isspace((unsigned char)*endptr))
      ++endptr; // skip whitespace

    if (*endptr == '\0') {
      *out = val;
      return 0; // success
    }
  }
  return -1; // error
}

/** print integer partition: a[1] + a[2] + ... + a[size-1] */
static void
print_integer_partition(size_t size, nonneg_t a[size]) {
  for (size_t i = 1; i < size; ++i) {
    if (a[i] == 0)
      break;
    if (i != 1)
      printf(" + ");
    printf("%" NONNEG_PRI, a[i]);
  }
  printf("\n");
}

/** Donald E. Knuth, TAOCP Volume 4A, 7.2.1.4. "Generating all partitions"
    Algorithm P
    http://cs.utsa.edu/~wagner/knuth/fasc3b.pdf
 */
static void
generate_integer_partitions(size_t size, nonneg_t a[size],
			    void (*visit)(size_t, nonneg_t*)) {
  nonneg_t n = size - 1;
  if (n == 0) {
    visit(size, a); // visit empty partition
    return;
  }
  //P1
  a[0] = 0;
  size_t m = 1;
  for ( ; ; ) { //P2
    a[m] = n;
    nonneg_t q = m - (n == 1);
    for ( ; ; ) { //P3
      visit(m+1, a);
      if (a[q] == 2) { //P4
	a[q] = 1;
	q -= 1;
	m += 1;
	a[m] = 1;
	continue; // goto P3
      }
      else { //P5
	if (q == 0)
	  return;
	nonneg_t x = a[q] - 1;
	a[q] = x;
	for (n = m - q + 1, m = q + 1; x < n; m += 1, n -= x) //P6
	  a[m] = x;
	break; // goto P2
      }
    }
  }
}