/* combinations.c  generate all combinations of n things taken m at a time */
/* return is 0 if more combinations to come. 1 if this is last             */
/* n is for n things     n! / ((n-m)! m!) combinations                     */
/* m is for m at a time                                                    */
/* vn must be the n items, unchanged by comb (can by pointers or indices)  */
/* vm must be of size m items, the returned combination each call          */
/* first must be 1 the first call, then set to zero internally             */

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

int combinations(int n, int m, int vn[], int vm[], int *first)
{
  static int *c;  /* the combination array */
  static pos;     /* position of variable being moved, 0 to n-1 */
  static var;     /* variable being moved, 0 to m-1 */
  static mov;     /* variable starting move, 0 to m-1 */
  int empty = -1; /* mark empty space */
  int i, j, k;
  
  if(m<1 || m>n)
  {
    printf("bad parameters to comb, n=%d, m=%d\n", n, m);
    return 1;
  }

  if(*first)
  {
    *first = 0;
    c = (int *)calloc(n, sizeof(int));
    if(c == NULL)
    {
      printf("malloc failed to allocate %d bytes\n", n);
      return 1;
    }
    for(i=0; i<n; i++)
    {
      if(i<m)
      {
        c[i] = i;
        vm[i] = vn[i]; /* first combination */
      }
      else  c[i] = empty;
    }
    pos = m-1;
    var = 0;
    mov = 0;
    if(m==n) return 1; /* only one combination */
    return 0;
  }

  /* non first case */
  if(pos<n-1) /* simple position, increment last, m-1, item */
  {
    if(c[pos+1]!=empty)
    {
      printf("pos error pos=%d, var=%d, mov=%d, c[pos]=%d, c[pos+1]=%d \n",
             pos, var, mov, c[pos], c[pos+1]);
      return 1;
    }
    c[pos+1] = c[pos];
    c[pos] = empty; /* mark empty space */
    pos++;
    vm[m-1] = vn[pos]; /* set new combination */
    /* printf("check pos=%d, var=%d, mov=%d, c=%d", pos, var, mov, c[0]);
       for(j=1; j<n; j++) printf(" %d", c[j]);
       printf("\n"); */
    if(m==1 && pos==n-1) return 1; /* finished */
    return 0; 
  }

  /* must back up case */
  c[n-1] = empty;
  mov = n;
  j = 0;
  for(i=n-2; i>=0; i--)
  {
    if(c[i]!=empty) c[i] = empty;
    else {j=i; break; }
  }
  for(i=j; i>=0; i--) /* n-1 last used if we get here */
  {
    if(c[i]!=empty)
    {
      var  = c[i];
      c[i] = empty;
      mov  = i+1;   /* start new sequence */
      pos  = mov+1;
      break;
    }
    else c[i] = empty;
  }
  if(mov==n)
  {
    printf("comb error  c[0]=%d, c[1]=%d, c[2]=%d, c[3]=%d \n",
                     c[0], c[1], c[2], c[3]);
    return 1;
  }
  for(i=mov; i<n; i++)
  {
    c[i] = var;
    vm[var] = vn[i];
    var++;
    pos = i;
    if(var==m) break;
  }
  
  /* printf("check pos=%d, var=%d, mov=%d, c=%d", pos, var, mov, c[0]);
     for(j=1; j<n; j++) printf(" %d", c[j]);
     printf("\n"); */
  if(c[mov]==0 && mov>=n-m) return 1; /* last combination */
  return 0;
} /* end combinations.c */