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

/*
 * Class Name : Permutations.java
 * Composed of 3 public methods
 *	- main - responsible for I/O mainly
 *  - constructor - responsible for taking in
 *        the integer parameter (n) and initializing
 *		  various arrays appropriately according
 *        to this variable
 *	- displayPermutations - counts and displays
 *        all the permutations of the integers
 *        from 1 to n in order of minimal difference
 *			- makes a call to a private method
 *				"nextPerm" which calculates each
 *              permutation
 */


public class Permutations
{

	/*GLOBAL VARIABLES USED IN 
	  CALCULATION OF PERMUTATIONS*/
	
	// A boolean array keeps track of the direction 
	//   each digit of the permutation is moving 
	//   when the next permutation is calculated.
	boolean [] direction; 
	
	// This variable holds the value of the 
	//	 user-defined integer parameter that 
	//	 represents the number of digits that 
	//	 are to be permutated.
	int maxNum;
	
	// An integer array holds the digits of the 
	//	 current permutation.
	int [] perms;
	





	/* main
	 * Description of Action: prompts the user for an 
	 *	    integer input (n) and upon input, calls 
	 * 		the methods responsible for displaying
	 *      the permutations of the integers from 
	 * 		1 to n in order of minimal difference
	 */
	public static void main( String [] args )
	{
		BufferedReader in = 
		   new BufferedReader( new InputStreamReader( System.in ) );
		String line;
		StringTokenizer str = null;
		String numStr, option;
		char optChar;
		int number;
		
		boolean done = false;
		
		// While the user still wants to run the program
		//	  to display permutations.......
		while( !done ) 
		{
			System.out.print("\nEnter the number of digits "+
				"to be permutated \nin minimal difference order" +
				" (0 to quit) :\t");
			
			try
			{
				line = in.readLine(); // Read input from the user.
				str = new StringTokenizer( line );
				while( !str.hasMoreTokens() )
				{
					line = in.readLine();
					str = new StringTokenizer( line );
				}
				
				numStr = str.nextToken();
				
				// number = (user-defined integer)
				number = Integer.parseInt(numStr); 
				
				// If the input integer is a 0, quit the program.
				if(number==0) 
				{
					System.out.println("\nHave a wonderful day!!");
					System.out.println("Thank-you and goodbye :)\n");
					done = true;
				}
				
				// If the input integer is <= 6, 
				//		display the permutations.
				else if(number<=6) 
				{
					System.out.println();
					
					//Initialize a Permutations object called "test"
					//  using the integer parameter supplied by the 
					//  user ( see method marked with "*****1*****" 
					//  for code ).
					Permutations test = new Permutations( number );
					
					// Display all permutations in minimal 
					//  difference order ( see method marked with 
					//  "*****2*****" for code ).
					test.displayPermutations();	
				}
				
				// If the input integer is > 6, print a message 
				//		warning of the large number of permutations 
				//		and ask the user if he/she wishes to 
				//		display them all.
				else 			
				{
					int tooMany=1;
					
					// Calculate the number of permutations 
					//	for the input.
					for(int i=number ; i>0 ; i--)
						tooMany *= i;
					
					System.out.println("\nThere are " + tooMany +
						" permutations of " + number + " digits.");
					System.out.print("Are you sure you want " +
						"to view them all? (Y/N) :\t");
					
					line = in.readLine();
					str = new StringTokenizer( line );
					while( !str.hasMoreTokens() )
					{
						line = in.readLine();
						str = new StringTokenizer( line );
					}
					
					option = str.nextToken();
					optChar = option.charAt(0);
					
					//	If user decides to view the permutations, 
					//		then display them all.
					if( optChar == 'y' || optChar == 'Y' )
					{
						// Initialize a Permutations object called 
						//  "test" using the integer parameter 
						//  supplied by the user ( see method marked 
						//	with "*****1*****" for code ).
						Permutations test = new Permutations(number); 
						
						// Display all permutations in minimal 
						//   difference order( see method marked 
						//	 with "*****2*****" for code ).						
						test.displayPermutations();
					}
				}
	 		}
	 		
	 		// The 'catch' statement is run if the 
	 		//	user input is not an integer.
	 		catch( Exception e )
			{      
				System.out.println("\nPlease enter integer " +
					"values only.");		
			}
		}
	}
	


	/*
	 * Permutations - constructor
	 * Parameter: n, the integer number of digits 
	 *    from 1 to n to be permutated
	 * Description of Action : 
	 *    - sets the variable "maxNum" to the parameter "n"
	 *    - creates a boolean array that has "maxNum" number of 
	 *			idicies which keep track of the direction that 
	 *			each number from 1 to maxNum is moving when the
	 *			next permutation is calculated.
	 *				- false designates movement to the left
	 *				- true  designates movement to the right
	 *			** Note : the direction of movement set for the 
	 *				         integer 1 is stored in index 1-1=0 
	 *						 of the array,
	 *					  the direction of movement set for the 
	 *					  	 integer 7 is stored in index 7-1 or 
	 *						 6 of the array, etc.
	 *	  - creates an array to hold the digits of each 
	 *			permutation and such it is the same size as 
	 *			"maxNum", the parameter
	 */
	public Permutations( int n )	/*****1*****/
	{
		maxNum = n;
		
		// Initialize the size of the direction array ( that is 
		//	holding the direction that each number from 1 to 
	 	//	maxNum is moving when the next permutation is 
	 	//	calculated ) to maxNum.
		direction = new boolean[maxNum];
		
		// Initialize each index of the array to false so that 
		//   the direction set for movement of each of the 
		//   integers from 1 to maxNum is left (denoted by 
		//	 boolean false).
		for( int i=0 ; i<direction.length ; i++ )
			direction[i] = false; 
			
		// Initialize the size of the integer array holding 
		//	 each permutation to the user-defined input integer
		//   "maxNum".
		perms = new int [maxNum];
	}
	
	/* 
	 * Method to display all the permutations in order by 
	 * minimal difference.  This code always runs after 
	 * the above constructor code ( see code marked with 
	 * "*****1*****" ) has run.
	 */
	public void displayPermutations()	/*****2*****/
	{
		int factorial = maxNum;
		int reps = 1;	
		
		//variable used to display a count of the	
		//   permutations on the user's screen
		int countReps = 1; 
						   
		
		// Initialize each index in the array to values 1...n.
		for( int i=0 ; i<maxNum ; i++ )
		{
			perms[i] = i+1;
		}
		
		// Calculate the total number of permutations 
		//	by caluculatingthe factorial of the 
		//  user-defined input integer (stored in 
		//	variable "factorial") and store this value 
		//	in the variable "reps".
		while( factorial>0 )
		{
			reps = reps*factorial;
			factorial--;
		}
		
		
		System.out.print( "\t" + countReps++ + ".\t");
		
		// Print the first permutation ( which has the 
		//	digits in order ) on the screen.
		for( int i = 0 ; i<maxNum ; i++ )
		{
			System.out.print( perms[i] );
		}
			
		System.out.println();
		
		// Decrement the number of permutations remaining.
		reps--; 
		
		// While there are still more permutations left.....
		while( reps > 0 )
		{
			// Calculate the next permutation by calling 
			//   the nextPerm method ( see method marked 
			//	 with "*****3*****" for code ) and pass
			//   the perms array holding the current 
			//   permutation and the direction array 
			//   holding the current direction of 
			//   movement for each digit as parameters.  
			//   The next permutation will overwrite the 
			//	 old one in the perms array.
			nextPerm( perms , direction );
			
			System.out.print( "\t" + countReps++ + ".\t");
			
			// Print the digits of the current permutation
			//   stored in the perms array on the screen.
			for( int i = 0 ; i<maxNum ; i++ )
			{
				System.out.print( perms[i] );
			}
			
			System.out.println();
			
			// Decrement the number of permutations remaining.
			reps--;	
		}


	}
	
	/*
	 * Calculate the next permutation of the consecutive 
	 * 		integers storedin array using minimal 
	 *  	difference order and store this permutation 
	 * 		back into the array.
	 * Parameters: array, the integer array containing 
	 *					the current permutation of digits
	 *			   dir, the boolean array storing the 
	 *				    direction that each of the digits 
	 *					of the current permutation is 
	 *			        moving in the minimal difference 
	 *					sequence of permutations
	 *					** Note : the direction of movement 
	 *								set for the integer 1
	 *				      	 		is stored in index 
	 *								1-1=0 of the array,
	 *					  		  the direction of movement 
	 *								set for the integer 7
	 *					  			is stored in index 7-1 
	 *								or 6 of the array, etc.
	 */	 
	 private void nextPerm( int [] array , boolean [] dir )	/***3***/
	 {
		int i;
		int [] temp;
		
		/* Note : array.length = length of the integer array 
									called "array"
							   = the largest digit in the set 
							   		of permutations */
		
		
		// CASE 1:
		// If the direction of the largest digit is set to left
		//	and it is not the first digit of the permutation......
		//	... then calculate the next permutation by simply moving
		//	the largest digit one position to the left.
		if( dir[array.length - 1]==false && array[0] != array.length)
		{
			// Locate the index of the array 
			//	 containing the largest digit.
			for(i=1 ; i<array.length && array[i]!=array.length ; i++)
				; 
			
			// Move the largest digit to the left by switiching 
			// 	it with the integer contained in the index of
			//  the array before it.
			array[i] = array[i-1];
			array[i-1] = array.length;
		}
		
		
		// CASE 2:
		// If the direction of the largest digit is set to right
		//	and it is not the last digit of the permutation......
		//	... then calculate the next permutation by simply moving
		//	the largest digit one position to the right.
		else if( dir[array.length - 1] == true 
			&&array[ array.length - 1 ] != array.length )
		{
			// Locate the index of the array 
			//	containing the largest digit.
			for(i=0;i<(array.length-1) && array[i]!=array.length ;i++)
				;
		
			// Move the largest digit to the right by switiching 
			//	it with the integer contained in the index of
			//  the array after it.
			array[i] = array[i+1];
			array[i+1] = array.length;		
		}
		
		
		// CASE 3:
		// If the direction of the largest digit (call it n) 
		//	is set to left and it is the first (leftmost) 
		//	digit of the permutation......
		//	... then calculate the next permutation by taking 
		//	the order of the digits from 1 to n-1 and finding 
		//  the next permutation of their order (using a 
		//	recursive call to this method with a temp array
		//	containing only these digits) and then attaching 
		//  the largest digit (n) to the left end of the new 
		//	permutation of the n-1 digits.  Also set the 
		//  direction of the largest digit (n) to move to the
		//  right now by changing the appropriate index in 
		//	the dir array to true.
		else if(dir[array.length-1]==false && array[0]==array.length)
		{
			// Set the direction of movement of 
			//	the largest integer to right.
			dir[array.length-1] = true; 
			
			// Initialize a temp array to hold 
			//	the digits from 1 to (n-1).
			temp = new int [array.length - 1];
			
			// Store the digits from 1 to (n-1) 
			//	in the temp array in the order
			//	that they occur in the original 
			//	array.
			for( i=1 ; i<array.length ; i++ )
			{
				temp[i-1] = array[i];
			}
			
			// Make a recursive call to the method 
			//	using the smaller temp array so as 
			//	to retrieve the next permutation of 
			//	these digits separately.
			nextPerm( temp, dir ); 
			
			// Leave the largest digit in the 
			//	leftmost index (0) of the original 
			//	array and copy the new permutation 
			// 	of the integers from 1 to n-1 into 
			//  the indicies of the original array 
			//	that follow
			for( i=1 ; i<array.length ; i++ )
			{
				array[i] = temp[i-1];
			}
		}
		
		
		// CASE 4:
		// If the direction of the largest digit (call it n) 
		//	is set to right and it is the last (rightmost) 
		//	digit of the permutation......
		//	... then calculate the next permutation by taking 
		//	the order of the digits from 1 to n-1 and finding 
		//	the next permutation of their order (using a 
		//	recursive call to this method with a temp array
		//	containing only these digits) and then attaching 
		//	the largest digit (n) to the right end of the new 
		//	permutation of the n-1 digits.  Also set the 
		//	direction of the largest digit (n) to move to the 
		//	left now by changing the appropriate index in the 
		//	dir array to false.
		else if( dir[array.length-1]==true 
			&& array[ array.length - 1 ] == array.length )
		{
			// Set the direction of movement of 
			//	the largest integer to left.
			dir[array.length-1] = false;
			
			// Initialize a temp array to hold the 
			//	digits from 1 to (n-1).
			temp = new int [ array.length - 1 ] ;
			
			// Store the digits from 1 to (n-1) in 
			//	the temp array in the order that 
			//	they occur in the original array.
			for( i=0 ; i < (array.length-1) ; i++ )
			{	temp[i] = array[i];	}
			
			// Make a recursive call to the method 
			//	using the smaller temp array so as 
			//	to retrieve the next permutation of 
			//	these digits separately.		
			nextPerm( temp , dir );
			
			// Leave the largest digit in the 
			//	rightmost index of the original array
			// 	and copy the new permutation of the 
			//	integers from 1 to n-1 into the 
			//	indicies of the original array that 
			//	precede.
			for( i = 0 ; i<(array.length-1) ; i++ )
			{
				array[i] = temp[i];
			}
		}
		
	}
		
}