import java.util.Enumeration;
import java.util.NoSuchElementException;

final class Permute implements Enumeration {

  /**
   * Next permutation array
   */
  private int a[]=null;

  /**
   * Given an array a, consisting of unique integers, will
   * produce the next lexicographic permutation.
   * @param a Array of UNIQUE integers
   * @return Next lexicographic permutation
   * @exception ArrayIndexOutOfBounds 
   *  if the input array represents the greatest possible permutation
   */
  private final int[] nextPerm(int a[]) {
    int i,j;
    for(i=a.length-2; a[i]>a[i+1]; i--);
    for(j=a.length-1; a[i]>a[j]; j--);
    int t=a[i]; a[i]=a[j]; a[j]=t;
    int b[]=(int [])a.clone();
    for(j=i+1; j<a.length; j++)
      b[j]=a[a.length+i-j];
    return b;
  }

  /**
   * Initialise a permutation enumeration with
   * an array {0,1,...,n-1}.
   */
  public Permute(int n) {
    a=new int[n];
    for(int i=0; i<n; i++)
      a[i]=i;
  }

  /**
   * Is another permutation available?
   */
  public boolean hasMoreElements() {
    return a!=null;
  }

  /**
   * Generate next permutation in lexicographic sequence
   */
  public Object nextElement() {
    if (a==null) throw new NoSuchElementException();
    int cur[]=(int [])a.clone();
    try {
      a=nextPerm(a);
    }
    catch (ArrayIndexOutOfBoundsException e) {
      a=null;
    }
    return cur;
  }

  /**
   * Returns factorial of n
   */
  private static int fact(int n) {
    int f=1;
    for(int i=1; i<n+1; i++) 
      f*=i;
    return f;
  }

  /**
   * Return a table of permutations of an
   * array {0,1,..,n-1}
   */
  public static int[][] createTable(int n) {
    int a[][]=new int[fact(n)][];
    Enumeration e=new Permute(n);
    for(int i=0;i<a.length;i++)
      a[i]=(int[])e.nextElement();
    return a;
  }

  /**
   * Return indices into sorted table representing
   * shorter permutations, from a the larger set
   */
  public static int[][] createIndices(int n) {
    int indices[][]=new int[n][];
    int total=fact(n);
    for(int i=0; i<indices.length; i++) {
      int size=total/fact(n-i-1);
      int factor=total/size;
      indices[i]=new int[size];
      for(int j=0, cur=0; j<size; j++, cur+=factor)
        indices[i][j]=cur;
    }
    return indices;
  }

  /**
   * Test the permutation engine
   */
  public static void main(String args[]) {
    final int size=7;
    System.out.println("create table...");
    int table[][]=createTable(size);
    System.out.println("create index...");
    int index[][]=createIndices(size);
    System.out.println("dump indices...");
    for(int i=0; i<index.length; i++) {
      System.out.println("----- "+(i+1)+": "+index[i].length);
      for(int j=0; j<index[i].length; j++) {
        StringBuffer s=new StringBuffer("");
        for(int k=0; k<i+1; k++)
          s=s.append(table[index[i][j]][k]).append(" ");
        System.out.println(s);
      }
    }
    System.out.println("done.");
  }
}