/* Algorithm 4.7 from Ruskey's textbook: A procedure for generating B(n, k) in colex order that is CAT if k ≤ n/2. */
/* CAT-ness is achieved by the PET technique #1.  */
/* In this case, that means initialisation with 0's and eliminating 0-paths from the recursion tree by
   stopping the recursion when k == 0 rather than when n == 0. */

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

#define MAX 50

int size;

void PrintIt(int Array[]) {
  int i;
  
  for (i = 0; i < size; i ++) printf(" %d", Array[i]);

  printf("\n");
}

void Combs(int Array[], int n, int k) {
  int i;

  if (k == 0)
    /* w.r.t. the non-PET version, the part of the function that fills in 0's is removed. */
    PrintIt(Array);
  else {
    if (k < n) {
      /* Array[n-1] = 0; */
      Combs(Array, n-1, k); }
    /* no need to check if k > 0 as in comb-rec-bitstring-colex.c! */
    /*  w.r.t. the non-PET version, the part of the function that fills in 1's remains. */
    Array[n-1] = 1;
    Combs(Array, n-1, k-1);
    Array[n-1] = 0;
  }
}

int main(int argc, char *argv[]) {
  int n, k, i;
  int B[MAX];
  
  if (argc != 3) {
    printf("\n Two arguments expected.\n");
    return 1;
  }

  k = atoi(argv[1]);
  n = atoi(argv[2]);

  if (n < 0 || k < 0) {
    printf("\n Positive numbers expected.\n");
    return 2;
  }

  if (n > MAX || k > MAX) {
    printf("\n Numbers not greater than %d expected.\n", MAX);
    return 3;
  }

  if (k > n) {
    printf("\n The first number must not be greater than the second number.\n");
    return 4;
  }

  for (i = 0; i < MAX; i++) B[i] = 0;
  size = n;
  
  Combs(B, n, k);
  
  return 0;
}