/* b150.c

xref:  b091.c

input: stdin

output: stdout

does:   - list all sequences of n 0/1 numbers such that

          at each |#1(t) - #0(t)| <= 2, t=1:n.

        - allow user input of max  |#1(t) - #0(t)|

*/

/************************************************************/

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <time.h>

/***********************************************************/



#define   MAXN  30



int global_maxd;

int global_n;

int global_m = 0;



void path  (int a[], int t, int d);

void process (int a[], int n);

int get_int (int lower, int upper, char* label);

void report_time (clock_t t1, clock_t t2);



/*************************************************/



main()

{



  int a[1+MAXN];

  int n, m, t;

  clock_t t1, t2;

  double time, mv[3];



  printf("This program lists all sequences of n 0/1 numbers such that\n");

  printf("at each t=1,...n, |#1(t) - #0(t)| <= 2.\n");



  global_n = get_int (1, MAXN, "Input n = ");

  global_maxd = get_int (1, global_n, "Input maximum |#1(t) - #0(t)| = ");



  t1 = clock();       /* start the clock */

  path (a, 1, 0);      /* all paths */

  t2 = clock();       /* stop the clock */





  printf ("n=%d\n", global_n);

  printf ("%d sequences", global_m);



  report_time (t1, t2);

}



/*************************************************/



void process (int a[], int n)

/* process the array a[1:n]     */

{

  int i;



  for (i = 1; i <= n; i++)

    printf ("%d", a[i]);



  printf ("\n");

  global_m ++;

}

/*************************************************/



void path  (int a[], int t, int d)



/* generate all the paths from t to n  */

/* d := #1(t-1) - #0(t-1) */

/* pass them, one at a time, to process() */

/* recursive */



{

  if (t > global_n)   process(a, global_n);  /* recursion ends here */

                               /* output one path */



  else  if (d == (-global_maxd)) {   /* next can only be 1 */

    a[t] = 1;                  /* set a[t] */

    path (a, t+1, -(global_maxd-1));         /* get path a[t+1:n]  */

  }

  else  if (d <  global_maxd)  {   /* -MAXD < d < MAXD */

    a[t] = 0;                  /* set a[t] */

    path (a, t+1, d-1);        /* get path a[t+1:n]  */



    a[t] = 1;                  /* set a[t] */

    path (a, t+1, d+1);        /* get path a[t+1:n]  */

  }

  else                      {   /* d =  global_maxd */

    a[t] = 0;                  /* set a[t] */

    path (a, t+1, (global_maxd-1));         /* get path a[t+1:n]  */

  }

};

/*************************************************/



int get_int (int lower, int upper, char* label)

/* returns an integer between lower and upper read from stdin */

/* abort the program if input is out of range */

{

  int n;



  printf("%s", label);

  scanf("%d", &n);

  printf("\n");



  if ((n < lower) || (n > upper))

  {

    printf("%d is invalid, value must be between %d and %d\n", n, lower, upper);

    printf("program is aborted\n");

    exit(1);

  }

  return n;

}

/*************************************************/



void  report_time (clock_t t1, clock_t t2)

{

  double time;



  time =  ((double) (t2-t1)) / CLOCKS_PER_SEC;

  printf("\nTime used = %g seconds.\n", time  );

}