/*
 * World's worst sorting algorithm:  examine all possible permutations
 * of the array contents and select the one that has NO elements out
 * of order.  Note that this is an OPTIMAL method if the data are
 * already sorted:  n-1 comparisons to termination if the permutations
 * are examined as they are generated.
 *
 * Author:  Timothy Rolfe
 */

public class PermSort
{
   // Test whether there are no out-of-order pairs in the array
   static boolean test ( Comparable[] x )
   {
      for ( int k = 1; k < x.length; k++ )
         if ( x[k-1].compareTo(x[k]) > 0 )
            return false;         // out of order at [k]
      return true;                // No pairs out of order
   }

   static void swap ( Comparable[] x, int p, int q )
   {  Comparable tmp = x[p]; x[p] = x[q]; x[q] = tmp;  }

   static void permSort ( Comparable[] x )
   {  permSort (x, 0);  }

   // Generate all permutations of element and examine them
   static boolean permSort ( Comparable[] x, int posn )
   {
      int size = x.length;

      if ( posn == size )    // I.e., a complete permutation
         return test(x);
      else
      {  Comparable tmp;     // Hold cell contents during rotation
         int        k;       // Loop variable

         for ( k = posn; k < size; k++ )
         {//Swap next candidate into [posn]
            swap (x, k, posn);
         // then ship it forward for testing when complete.
            if ( permSort(x, posn+1) )
                  return true;
         }
      // The loop above ends with the array [posn ... size-1] having
      // undergone a right-rotation by one element.  It is critical
      // that this be undone so that when we backtrack, the proper
      // value is in place to be used next for [posn-1].
         tmp = x[posn];
         for ( k = posn+1; k < size; k++ )
            x[k-1] = x[k];
         x[size-1] = tmp;
      }
      return false;          // Keep looking.  This one didn't work.
   }

   // Completely randomize positions within x[] from [0] to [n-1]
   static void shuffle (Comparable[] x, int n)
   {  while ( n > 1 )
      {  int k = (int) (Math.random() * n--);

         swap (x, k, n);
      }
   }

   static public void main ( String[] args )
   {  Data    x[];      // Array to be sorted
      int     size,     // Requested size for x
              k;        // Loop variable
      boolean chk;      // Result from permSort
      long    fact = 1;
      long    nCmp;
      java.util.Scanner console = new java.util.Scanner(System.in);

      System.out.print ("Size:  ");
      if ( args.length == 0 )
         size = console.nextInt();
      else
      {  size = Integer.parseInt(args[0]);  System.out.println(size);  }

      x = new Data[size];
      for ( k = 0; k < size;  )
      {  x[k] = new Data(size - k);
         fact *= ++k;
      }

      System.out.println (size + " gives " + fact + " possible sequences.");

   // The Data objects are reversed by the for loop above
      nCmp = Data.nCompares();    // Zero out the counter
      permSort(x, 0);
      nCmp = Data.nCompares();    // Capture the comparison count
      System.out.println ("Reversed data.");
      for ( k = 0; k < size; k++ )
         System.out.print ("  " + x[k]);
      System.out.println (" --- " + nCmp + " comparisons.");

   // Completely randomize the data
      shuffle (x, size);
      nCmp = Data.nCompares();    // Zero out the counter
      permSort(x, 0);
      nCmp = Data.nCompares();    // Capture the comparison count
      System.out.println ("Random data.");
      for ( k = 0; k < size; k++ )
         System.out.print ("  " + x[k]);
      System.out.println (" --- " + nCmp + " comparisons.");

   // Data left sorted from previous run.
      nCmp = Data.nCompares();    // Zero out the counter
      permSort(x, 0);
      nCmp = Data.nCompares();    // Capture the comparison count
      System.out.println ("Sorted data.");
      for ( k = 0; k < size; k++ )
         System.out.print ("  " + x[k]);
      System.out.println (" --- " + nCmp + " comparisons.");
   }

   static class Data implements Comparable
   {  static private long nCompares = 0;
      private int value;
   
//    Default constructor
      Data ()
      {  value = 0;  }
   
//    Initializing constructor
      Data (int value)
      {  this.value = value;  }
   
//    Copy constructor
      Data (Data item)
      {  value = item.value;  }
   
      public void set(int value)
      {  this.value = value;  }
   
      public int  get()
      {  return value;  }
   
      public String toString()
      {  return Integer.toString(value);  }
   
      public int compareTo ( Object right )
      {  nCompares++;
         return this.value - ((Data)right).value;
      }
   
      static public long nCompares ()
      {  long temp = nCompares;
   
         nCompares = 0;
         return temp;
      }
   }
}
/* Specimen execution of the above code:

Size:  16
16 gives 20922789888000 possible sequences.
Reversed data.
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 --- 524272 comparisons.
Random data.
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 --- 357945 comparisons.
Sorted data.
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 --- 15 comparisons.
*/