//
//  Permute.java
//  Permute
//
//

import java.io.*;
import java.util.*;

public class Permute {

    private static void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

   // this method is the answer to the assignment
   
    private static void permute(char [] str, int low, int high)	{

        if (low == high) {		//if at end of string print out permutation
            System.out.println(new String(str));
        }
        else {
            for (int i = low; i <= high; i++)	{
                swap(str, i, low);		
                permute(str, low + 1, high);			
                swap(str, i, low);
            }
        }
    }

    // the following algorithm, by Fedor Labounko, preserves lexicographic ordering 
    
    private static void lexPermute(char [] str, int low, int high)	{

        if (low == high) {		
            System.out.print(new String(str));
            System.out.print("  ");
        }
        else {
            for (int i = low; i <= high; i++)	{
                collapse(str, i, low);
                lexPermute(str, low + 1, high);			
                uncollapse(str, i, low);
                if(low == 0) {}
                    //System.out.println();
            }
        }
    }

	private static void collapse(char[] str, int i, int low) {
		char temp = str[i];
        for(int j = i; j > low; j--) str[j] = str[j-1];
        str[low] = temp;
	}
	
	private static void uncollapse(char[] str, int i, int low){
		char temp = str[low];
        for(int j = low; j < i; j++) str[j] = str[j+1];
		str[i]=temp;
	}

    public static void permute(String str) {
        System.out.println("Lexicographic: ");
        long start = new Date().getTime();
        lexPermute(str.toCharArray(), 0, str.length() - 1);
        long stop = new Date().getTime();
        long elapsed = stop - start;
        System.out.println("Elapsed time: " + elapsed + " milliseconds");

        System.out.println("Non-lexicographic: ");
        start = new Date().getTime();
        permute(str.toCharArray(), 0, str.length() - 1);
        stop = new Date().getTime();
        elapsed = stop - start;
        System.out.println("Elapsed time: " + elapsed + " milliseconds");

    }
    
    public static void main( String [ ] args ) {
        BufferedReader in = new BufferedReader( new
                                 InputStreamReader( System.in ) );
        System.out.println( "Enter string to permute: " );
        try {
            String str = in.readLine( );
            permute(str);
        }
        catch( Exception e )
            { System.err.println( e.getMessage() ); }
    }
}