/** Perm.java -- illustrate how to generate permutations using recursion.
 *  adapted for lab
 */
import java.io.*;

public class Perm
{
  private int [] a;
  private int lastIndex;
  private String permString;
  
  // create an array of n elements containing the values 1..n
  // and start the permutations
  public Perm(int n)
  {
    a = new int[n];
    for (int i = 0; i < n; ++i)
      a[i] = i+1;
    permString = "";
    lastIndex = a.length - 1;
    permute(0);
  }

  /** Here is the recursive permute() function.  Compare this code to the
   *  output carefully to understand how it works.  We only generate a
   *  permutation once the first (left) index reaches the end.  In the
   *  recursive case, we have a LOOP for each index from here to the end.
   *  This makes sure that all permutations are generated.
   *  We temporarily swap elements, generate the recursive permutations, and
   *  swap back.
   */
  public void permute(int firstIndex)
  {
    if (firstIndex == lastIndex)
    {
      for (int i = 0; i <= lastIndex; ++i)
        permString += a[i] + " ";
      permString += "\n";
    }
    else
      for (int i = firstIndex; i <= lastIndex; ++i)
      {
        swap(firstIndex, i);
        permute(firstIndex + 1);
        swap(firstIndex, i);
      }
  } 

  public void swap(int x, int y)
  {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
  }

  public String toString()
  {
    return permString;
  }
}