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

// 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:
// Unlike the previous version of this problem, this version assumes
// that the input array may contain duplicates.

// Solution overview:
// This solution generates permutations recursively, just as the previous 
// version (that assumes no duplicates) does.  As we find permutations,
// we add each to a TreeSet, which ensures that we never have a duplicate.  
// We wait to output all the permutations until this process is complete.  
// An added bonus of our PermComparator implemenation, along with the 
// behavior of TreeSet, is that the permutations will be listed in
// lexicographic order!

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

public class Perm2
{
  private static TreeSet permList;  // set to hold our permutations

  public static void main( String[] args ) throws Exception
  {
    // get input from user:
    BufferedReader br = new BufferedReader(
                        new InputStreamReader( System.in ) );
    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 the permutations
    permList = new TreeSet( new PermComparator() );
    perm( theInts, 0, PERM_LEN - 1 );

    // display the permutations
    System.out.println( "The permutations: " );
    Iterator iter = permList.iterator();
    while( iter.hasNext() )
      System.out.println( iter.next().toString() );
  }

  // recursively generate permutations, and add each to permList.
  // The Set behavior of permList ensures that no duplicates actually get
  // added (depends on the proper functioning of our PermComparator 
  // below...)
  private static void perm( int[] list, int k, int m )
  {
    if ( k==m )
    {
      // list has one permutation, add it to the Set of permutations
      int[] tempPerm = new int[list.length];
      for( int i = 0; i <= m; i++ )
        tempPerm[i] = list[i];
      permList.add( new Permutation( tempPerm ) );
    }
    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.println( "Enter number of integers in original array : " );
    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;
  }

  // we have to add Objects to our Set (arrays don't qualify), so we use
  // this "wrapper" class to store our permutations
  private static class Permutation
  {
    public Permutation( int[] p )
    {
      this.p = p;
    }

    public String toString()
    {
      StringBuffer sb = new StringBuffer();
      for( int i = 0; i < this.p.length; i++ )
        sb.append( this.p[i] + " " );
      return new String( sb );
    }

    private int[] p;
  }

  // TreeSet calls this class's compare method to determine if two
  // objects are equal, as well as to determine in what order they fall
  private static class PermComparator implements Comparator
  {
    public int compare( Object o1, Object o2 )
    {
      Permutation p1 = (Permutation) o1;
      Permutation p2 = (Permutation) o2;
      // we'll just assume for this program that we don't need to
      // ensure that the permutations are equal length
      for( int i = 0; i < p1.p.length; i++ )
        if( p1.p[i] < p2.p[i] ) return -1;
        else if( p1.p[i] > p2.p[i] ) return 1;
      return 0;
    }
  }

}