/* Author:  Anil Seth
   Sep. 03   */
public class Enumeration{
     public static void perm(char[] a, int i){
            if (i==a.length-1) {print(a); return;}
            for(int j=i; j<a.length; j++){
                      perm(a,i+1);
                      rotateleft(a,i);
            }
     }
 
    public static void permNoRep(char[] a, int i){
         if (i==a.length-1) {print(a); return;}
            char[] b = new char[a.length-i];
            int pt=0;
            char ch;
            for(int j=i; j<a.length; j++){
                      ch = a[i];
   /* recursive calls are made only for distinct values of a[i],
      that is distinct values in i{th} position  */
                      if(!ArraySort.search(b,pt-1,ch))
                           {permNoRep(a,i+1); b[pt]=ch; pt++;}  
                      rotateleft(a,i);
             }
    }


     public static void permNoRepLex(char[] a, int i){
          if (i==a.length-1) {print(a); return;}
            char[] b = new char[a.length-i];
            int pt=0;
            char ch;
            char[] c = new char[a.length-i];
            for(int j=0; j<c.length; j++)c[j]=a[i+j];
            ArraySort.bubblesort(a,i);
            for(int j=i; j<a.length; j++){
                      ch = a[i];
                      if(!ArraySort.search(b,pt-1,ch))
                           {permNoRepLex(a,i+1); b[pt]=ch; pt++;}
                      rotateleft(a,i);
             }
            for(int j=0; j<c.length; j++)a[i+j]=c[j];
     }


     

          //Rotates the elements a[i] ... a[a.length-1]
          //circularly, counter clockwise by 1 position.
     public static void rotateleft(char[] a , int i){
            if (i==a.length-1) return;
            char t=a[i];
            for(int j=i; j<a.length-1; j++)a[j]=a[j+1];
            a[a.length-1] = t;
     }
 
          //Prints all the elements of array a in a line
     public static void print(char[] a){
            for(int i=0; i<a.length; i++)
                    System.out.print(a[i]+" ");
            System.out.println();
     }
     public static void main(String[] args){
            //Some test inputs for functions of
            //this class
            char[] b = {'a', 'b','a'};
            System.out.println("Unrestricted Permutaions");
            perm(b,0);
            System.out.println("Permutaions without repetitions");
            permNoRep(b,0);
            System.out.println("Permutaions without repetition in "
                                  +"lexicographic order");
            permNoRepLex(b,0);
            
            System.out.println("Unrestricted Permutaions");
            char[] a = {'a', 'b','c', 'a'};
            perm(a,0); 
            System.out.println("Permutaions without repetitions");
            permNoRep(a,0);
            System.out.println("Permutaions without repetition in "
                                  +"lexicographic order");
            permNoRepLex(a,0);
            
     }
}