import java.io.*;

// Permutations Programming Problem
// Input: An array size, followed by the specified number of integers
// Output: Each possible permutation of the input array of ints

// Assumpution:
// The input array contains no duplicate ints

// Implementation note:
// This solution generates permutations recursively.

// A nonrecursive solution is available at the contest website:
// http://cs.wcu.edu/cscontest

public class Perm
{
  public static void main( String[] args ) throws Exception
  {
    BufferedReader br = new BufferedReader(
                        new InputStreamReader( System.in ) );
    // get input from user:
    final int PERM_LEN = promptSize( br );
    int[] theInts = new int[PERM_LEN];

    System.out.println( "Enter the ints, each on a separate line:" );
    for(int i = 0 ; i < PERM_LEN; i++)
      theInts[i] = Integer.parseInt( br.readLine() );

    // find & display the permutations
    System.out.println( "The permutations: " );
    perm( theInts, 0, PERM_LEN - 1 );
  }

  // recursively find and display permutations
  private static void perm( int[] list, int k, int m )
  {
    if ( k==m )
    {
      // list has one permutation, output it
      for( int i = 0; i <= m; i++ )
        System.out.print( list[i] + " " );
      System.out.println();
    }
    else
    {
      // list[k:m] has more than one permutation
      // generate these recursively
      for( int i = k; i <= m; i++ )
      {
        swap( list, i, k );
        perm( list, k+1, m );
        swap( list, i, k );
      }
    }
  }

  // prompt user for permutation size; ensure it's at least 1
  private static int promptSize( BufferedReader br ) throws Exception
  {
    int p = 0;
    System.out.print( "Enter number of integers in original array : " );
    p = Integer.parseInt( br.readLine() );
    while( p < 1 )
    {
      System.out.print( "Please enter an array size of at least 1: " );
      p = Integer.parseInt( br.readLine() );
    }
    return p;
  }

  // swap a[i] and a[j]
  private static void swap( int[] a, int i, int j )
  {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

}