/* T03n01 - I got curious the other day, and decided to snoop around for an
 * fundamental algorithm that is O(n!).  As you might imagine, they are
 * rather hard to come by.  During my search, I found this web page:
 *    robsort.org
 * that has an implementation of an O(n!) sorting algorithm.  The site makes
 * the algorithm out to be more interesting that it really is, as the
 * algorithm is familiar to anyone who knows what permutations are.
 *
 * The algorithm:  Get a list of values.
 *                 Repeat  
 *                     Create a permutation.
 *                 Until the permutation is in sorted order.
 *
 * As there are n! permutations of a list of n values, it's clear that
 * the running time of the algorithm is O(n!).  This implementation is
 * ever-so-slightly dangerous, because it uses Java's Collections.shuffle()
 * class method to create permutations.  It doesn't create a nice, orderly
 * sequence of permutations; it just randomly slaps one together.  Thus, it
 * takes an unpredictable number of iterations to stumble upon the correct
 * sequence.  Theoretically, it may never find it.
 *
 * Note that I used Vectors in this program.  I thought, "I ought to do an
 * example with Vectors once in a while, if only to remind myself why I
 * dislike Vectors of base types."  I feel reminded.
 *
 * COMPILATION NOTE:  This was written for Java 1.4.  If using a Java 1.5
 * or later compiler, compile with the -source 1.4 flag.  Ex:
 *     javac -source 1.4 T03n01.java
 */

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

public class T03n01
{

    public static boolean isSorted (Vector list)
    {
        for (int i = 0; i < list.size()-1; i++) {
            if ( ((Integer)list.get(i)).compareTo(list.get(i+1)) > 0 ) {
                return (false);
            }
        }
        return (true);
    }


    public static int permutationSort (Vector list)
    {
        int permutations = 0;

        while (!isSorted(list)) {
            Collections.shuffle(list);
            permutations++;
        }

        return permutations;
    }


    public static long startTiming ()
    {
        System.gc();
        return (System.currentTimeMillis());
    }

    public static double stopTiming (long startingTime)
    {
        long elapsedTime = System.currentTimeMillis() - startingTime;
        return (elapsedTime / 1000.0);    // return seconds
    }


    public static void main (String[] args)
    {
        Vector list;
        long   startTime;
        double seconds;
        int    permutations;
        int    minutes;

        if (args.length == 0) {
            System.out.println("\nThis sorts a (small!) list of values using "
                             + "Permutation Sort, an O(n!) sort.\n");
            System.out.println("Usage: java T03n01 <element1> .. <elementN>");
            System.exit(1);
        }

        list = new Vector (args.length);
        for (int i = 0; i<args.length; i++) {
            list.add(i, new Integer(args[i]));
        }

        System.out.println("\nCalling PermutationSort on a list of size " 
                         + list.size() + ": " + list.toString());

        startTime = startTiming();
	permutations = permutationSort(list);
        seconds = stopTiming(startTime);
        minutes = (int)seconds / 60;
        seconds = (int)seconds % 60 + (seconds - (int)seconds);

        System.out.println("\nFinished!  The sorted list: " + list.toString() 
                         + "\n\n" + permutations + " permutations "
                         + "and " + minutes + " minutes, " 
                         + seconds + " seconds\nwere required to "
                         + "complete the sort.");

    }
}