/* Algorithm 4.8 from Ruskey's textbook: A procedure for generating A(n, k) in lex order that is CAT if k ≥ n/2. */
/* Ruskey is wrong about the order: the output is in lex order, not colex.  That is not a big deal, though.
   Colex output can be achieved by reverse printing. */
/* CAT-ness is achieved by a PET technique #1. */
/* In this case, that means initialisation with 1 .. k and stopping the recursion early --
   whenever we are at position k, n == k, and we are sure Array[1] = 1 .. Array[k] == k.
   The values 2,3,etc. in A[1] occur when n == k == 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 == n) PrintIt(Array);
  else {
    Combs(Array, n-1, k);
    if (k > 0) {
      Array[k-1] = n;
      Combs(Array, n-1, k-1);
      Array[k-1] = k;
    }
  }
}

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;
  }

  size = k;

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