// permute.java 
// CAUTION: N factorial permutations is a bunch for N > 9
// The precise definition of a bunch is 3,628,800 up
// 7! =   5,040   8! =  40,320    9! = 362,880 
// 13! overflows on a 32 bit machine or 32 bit compiler
//  INPUT:   vector - input and output vector that is permuted
//                    This must be set up befor the first call
//                    and then used as the next permutation on
//                    each return     
//      INIT:    permuters[0] != 0    typ = n+1, do not mess with
//      OUTPUT:  vector - the next permuted vector
// return false  if more permutations to be returned
//        true   if the last permutation is being returned (done)

public class permute
{
  public permute()
  {
  }

  public boolean perm(int n, int vector[], int permuters[])
  {
    int i,j,k,t;
    boolean if_last = false;
   
    if(n <= 1)return true;
    if(permuters[0] != 0)
    {
      // Initialization ( user must set up  vector  before first call 
      for(i=0;i<n;i++) permuters[i]=i;
    }
    else 
    {
      // find last in sequence of permuters 0's,reset permuters(k) to k as we go
      k = 0;
      while(permuters[k+1] == 0 && k<n)
      {
        k++;
        permuters[k] = k;
      }

      // reverse sequence  in  0 .. k 
      for(i=0;i<=k/2;i++)
      {
        j = k - i;
        t = vector[i];
        vector[i] = vector[j];
        vector[j] = t;
      }

      //  swap next higher item and decrement pointer 
      k++;
      permuters[k]--;
      j = permuters[k];
      t = vector[k];
      vector[k] = vector[j];
      vector[j] = t;

      //  find out if this is the last permutation 
      k = n-1;
      if(permuters[k] == 0)
      {
        while(k>0)
        {
          k--;
          if(permuters[k] != 0)
          {
            return if_last;
          }
        }
        if_last = true;
      }
    }
    return if_last;
  } // end perm

  public boolean permd(int n, double vector[], int permuters[])
  {
    int i,j,k;
    double t;
    boolean if_last = false;
   
    if(n <= 1)return true;
    if(permuters[0] != 0)
    {
      // Initialization ( user must set up  vector  before first call 
      for(i=0;i<n;i++) permuters[i]=i;
    }
    else 
    {
      // find last in sequence of permuters 0's,reset permuters(k) to k as we go
      k = 0;
      while(permuters[k+1] == 0 && k<n)
      {
        k++;
        permuters[k] = k;
      }

      // reverse sequence  in  0 .. k 
      for(i=0;i<=k/2;i++)
      {
        j = k - i;
        t = vector[i];
        vector[i] = vector[j];
        vector[j] = t;
      }

      //  swap next higher item and decrement pointer 
      k++;
      permuters[k]--;
      j = permuters[k];
      t = vector[k];
      vector[k] = vector[j];
      vector[j] = t;

      //  find out if this is the last permutation 
      k = n-1;
      if(permuters[k] == 0)
      {
        while(k>0)
        {
          k--;
          if(permuters[k] != 0)
          {
            return if_last;
          }
        }
        if_last = true;
      }
    }
    return if_last;
  } // end permd

  public boolean permc(int n, char vector[], int permuters[])
  {
    int i,j,k;
    char t;
    boolean if_last = false;
   
    if(n <= 1)return true;
    if(permuters[0] != 0)
    {
      // Initialization ( user must set up  vector  before first call 
      for(i=0;i<n;i++) permuters[i]=i;
    }
    else 
    {
      // find last in sequence of permuters 0's,reset permuters(k) to k as we go
      k = 0;
      while(permuters[k+1] == 0 && k<n)
      {
        k++;
        permuters[k] = k;
      }

      // reverse sequence  in  0 .. k 
      for(i=0;i<=k/2;i++)
      {
        j = k - i;
        t = vector[i];
        vector[i] = vector[j];
        vector[j] = t;
      }

      //  swap next higher item and decrement pointer 
      k++;
      permuters[k]--;
      j = permuters[k];
      t = vector[k];
      vector[k] = vector[j];
      vector[j] = t;

      //  find out if this is the last permutation 
      k = n-1;
      if(permuters[k] == 0)
      {
        while(k>0)
        {
          k--;
          if(permuters[k] != 0)
          {
            return if_last;
          }
        }
        if_last = true;
      }
    }
    return if_last;
  } // end permc

} // end class, permute.java