/*
  Authors: Gurmeet Singh Manku (manku@cs.stanford.edu)
           Joe Sawada (sawada@cis.uoguelph.ca)

  Summary:

  The input is an array t[m], t[m-1], ..., t[1]
  The output consists of all tuples (a[m], a[m-1], ..., a[1]) that satisfy
  two properties:

     I.   1 <= a[i] <= t[i],   for all m >= i >= 1.
    II.   If (a[i] = t[i])   then  (a[i-1] = 1)   for all m >= i > 1.

  The output is in Gray code order --- exactly one of the a[i]'s changes between
  successive listings.

  The algorithm is described in the following paper:

    "A Loopless Gray Code for Minimal Signed-Binary Representations"
    by Gurmeet Singh Manku and Joe Sawada, submitted to ESA 2005.

  Identification of the a[i] that gets changed between successive listings take
  O(1) time in the worst-case.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define EVEN(i) (((i) & 0x1) == 0)
#define ODD(i) (((i) & 0x1) == 1)

#define BRGC 100
#define BRGC_RESTRICT 200
// Change the following to BRGC if you wish to output plain "Binary Reflected Gray Code"
int type = BRGC_RESTRICT;

#define MAX_M 20
int m;
int max[MAX_M];
int a[MAX_M];
int delta[MAX_M];
int d[MAX_M];
int max[MAX_M];

int count = 0;  // Tracks the number of listings we have printed so far

void Print() {
  int i;

  for (i=m;   i>=1; i--)   printf(" %2d", a[i]);
  printf("    ");
  for (i=m+1; i>=1; i--)   printf(" %2d", delta[i]);
  printf("    ");
  for (i=m; i>=1; i--) {
    if (d[i] == -1) printf("  -");
    else printf(" %2d", d[i]);
  }
  printf("\n");
  count++;
}

void init() {
  int i, rev;

  switch (type) {
    case BRGC:
      for (i=m+1; i>=1; i--) delta[i] = i;
      for (i=m; i>=1; i--) a[i] = 1;
      for (i=m; i>=1; i--) d[i] = 1;
      break;

    case BRGC_RESTRICT:
      for (i=m+1; i>=1; i--) delta[i] = i;

      a[m] = d[m] = 1;

      if (EVEN(max[m])) rev = 1;
      else rev=0;

      for (i=m-1; i>=1; i--) {
        if (rev ==0) {
          a[i] = d[i] = 1;
          if (EVEN(max[i])) rev = 1;
        }
        else {
          a[i] = max[i];
          d[i] = -1;
          i--;
          a[i] = d[i] = 1;
          if (EVEN(max[i])) rev=0;
        }
      }
      break;

    default:
      printf ("ERROR");
      exit(-1);
  }
}

int is_terminal(int t) {
  return (a[t] == 1 || a[t] == max[t]);
}

void next(int t) {
  a[t] = a[t] + d[t];
}

int map(int t) {
  if (t >= 1 && t < m && a[t] == 1 && a[t+1] == max[t+1] && type == BRGC_RESTRICT) return(t+1);
  return (t);
}

void generate() {
  int t,u, last;

  while (1) {
    last = map(1);
    t = map(delta[last]);
    if (t == m+1) {
      printf("\ntotal = %d\n", count);
      exit(-1);
    }

    next(t);

    if (is_terminal(t)) {
      d[t] = -d[t];
      u = map(t+1);
      delta[t] = delta[u];
      delta[u] = u;
    }

    if (t != last) delta[last] = last;
    Print();
  }
}

int main() {
  int i, j, t, val;

  // parse the input
  fprintf(stdout, "\nEnter the values of t[m] t[m-1] ... t[1] (separated by whitespace): ");
  fflush(stdout);
  m = 0;
  while (fscanf(stdin, "%d", &val) == 1) {
    assert(val >= 2);
    assert(m < MAX_M);
    ++m;
    max[m] = val;
  }
  assert(m >= 2);

  // reverse max[]
  for (i=1,j=m; i<j; i++,j--)
    t=max[i],max[i]=max[j],max[j]=t;

  printf("\n");
  printf("See the following paper for explanation of the output:\n");
  printf("  \"A Loopless Gray Code for Minimal Signed-Binary Representations\"\n");
  printf("  by Gurmeet Singh Manku (manku@cs.stanford.edu) and Joe Sawada (sawada@cis.uoguelph.ca)\n");
  printf("\n");
  printf("The first  set of values is a[m] a[m-1] ... a[1]\n");
  printf("The second set of values is d[m] d[m-1] ... d[1]\n");
  printf("The third  set of values is p[m] p[m-1] ... p[1] ('-' represents -1)\n");
  printf("\n");

  init();
  Print();
  generate();
  return 0;
}