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];
7