// combinations.java   generate all combinations of n things taken m at a time 
// return is false if more combinations to come. true 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
// vm must be of size m items, the returned combination each call
// combinations(n,m) must be instantiated for each new series of combinations
// then more = comb(vn,vm) vn all index, vm m index, loop until more=false
// see sample use in  test_combinations.java

public class combinations
{
  private
  int n, m;
  int c[];  // the combination array 
  int pos;  // position of variable being moved, 0 to n-1 
  int var;  // variable being moved, 0 to m-1 
  int mov;  // variable starting move, 0 to m-1 
  int empty = -1; // mark empty space 
  boolean first;

  public combinations(int n, int m)
  {
    this.n = n;
    this.m = m;
    c = new int[n];
    for(int i=0; i<n; i++)
    {
      if(i<m)  c[i] = i;
      else     c[i] = empty;
    }
    pos = m-1;
    var = 0;
    mov = 0;
    first = true; 
  } // end combinations

  public boolean comb(int vn[], int vm[])
  {
    int j, k;
  
    if(m<1 || m>n)
    {
      System.out.println("bad parameters to comb, n="+n+", m="+m);
      return true;
    }
    if(first)
    {
      first = false;
      for(int i=0; i<m; i++)
      {
        vm[i] = vn[i]; // first combination 
      }
      if(m==n) return true; // only one combination
      return false; 
    }

    if(pos<n-1) // simple position, increment last, m-1, item 
    {
      if(c[pos+1]!=empty)
      {
        System.out.println("pos error pos="+pos+", var="+var+", mov="+mov+
                           ", c[pos]="+c[pos]+", c[pos+1]="+c[pos+1]);
        return true;
      }
      c[pos+1] = c[pos];
      c[pos] = empty; // mark empty space 
      pos++;
      vm[m-1] = vn[pos]; // set new combination 
      if(m==1 && pos==n-1) return true; // finished 
     return false; 
    }

    // must back up case 
    c[n-1] = empty;
    mov = n;
    j = 0;
    for(int i=n-2; i>=0; i--)
    {
      if(c[i]!=empty) c[i] = empty;
      else {j=i; break; }
    }
    for(int 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)
    {
      return true;
    }
    for(int i=mov; i<n; i++)
    {
      c[i] = var;
      vm[var] = vn[i];
      var++;
      pos = i;
      if(var==m) break;
    }
  
    if(c[mov]==0 && mov>=n-m) return true; // last combination 
    return false;
  } // end comb

} // end class, combinations.java