package bruthforth_tsp;

//----------------------------- Permutator ------------------------------------

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

/**
 * Permutator class gives an easy way to deal with permutations of an array of objects.<BR>
 */
class Permutator implements Enumeration,Serializable {
   private Object[] items;
   private int n;
   private int[] indexes;
   private int[] counter;
   private boolean firstTime=true;

   /** Constructs an enumeration of all permutations of the objects in the array 'objects' */
   public Permutator(Object[] items) {
      this.items=items;
      n=items.length;
      indexes=new int[n];
      counter=new int[n];
   }

   /** Constructs an enumeration of all permutations of {1,2,..n} */
   public Permutator(int n) {
      this(series(1,n));
   }

   /** Constructs an enumeration of all permutations of {k,k+1,...,m} */
   public Permutator(int k, int m) {
      this(series(k,m));
   }

   // ------------------------------ implementation -----------------------------------------------
   // we generate a permutation by selection, we first pick up the first item, then
   // pick up a second one from those that left and so on.
   // we have a counter that tells us the order of the selection for each permutation.
   // For example if we have 4 items: items={a,b,c,d}, and currently counter={2,1,1,0},
   // we will generate the next permutation by choosing first 'c' (the third item - 2 from 0),
   // then 'b' (the second (1) left of a,b,d), then 'd' and then 'a'.
   // after each permutation we advance the counter, were it's first place can go over 0..n-1, its
   // second trough 0..n-2 etc.
   // the indexes array keeps trace of which is the first, second,.. item in the remaining list.

   private void advanceCounter() {
      int i=n-1; // the last place is always 0, as there is only one choice for the last item.
      do {
         i--;
         if (i<0)
            throw new NoSuchElementException();
         counter[i]=(counter[i]+1)%(n-i); // for the i's place there are n-i remining choices
      } while (counter[i]==0);
   }

   public boolean hasMoreElements() {
      for (int i=n-2; i>=0; i--)
         if (counter[i]!=n-i-1)
            return true;
      return false;
   }

   public Object[] nextPermutation() {
      if (!firstTime)
         advanceCounter();
      else
         firstTime=false;
      Object[] permutation=new Object[n];
      for (int i=0; i<n; i++)
         indexes[i]=i;
      for (int i=0; i<n; i++) {
         int choice=counter[i];
         permutation[i]=items[indexes[choice]];  // choose the 'choice' item out of the remaining
         for (int j=choice; j<n-i-1; j++)  // update the indexes after the extraction
            indexes[j]=indexes[j+1];
      }
      return permutation;
   }

   public Object nextElement() {
      return nextPermutation();
   }

   private static Integer[] series(int from, int till) {
      Integer[] series = new Integer[till-from+1];
      for (int i=from; i<=till; i++)
         series[i-from]=new Integer(i);
      return series;
   }

   public static Object[] randomPermutation(Object[] items) {
      Permutator p = new Permutator(items);
      int n=items.length;
      int[] counter = new int[n];
      for(int i=0; i<n-1; i++)
         counter[i]=(int)(Math.random()*(n-i));
      p.counter=counter;
      p.firstTime=true;
      return p.nextPermutation();
   }

   public static int[] randomPermutation(int n) {
      Object[] permutation=randomPermutation(series(1,n));
      int[] result = new int[n];
      for (int i=0; i<n; i++)
         result[i]=((Integer)permutation[i]).intValue();
      return result;
   }

   /**
    * Lists the permutations of the command-line argument list.
    */
   public static void main(String[] args) {
      /*
      Permutator p = new Permutator(args);
      while (p.hasMoreElements()) {
         Object[] perm = p.nextPermutation();
         for (int i=0; i<perm.length; i++)
            System.out.print(perm[i]+", ");
         System.out.println();
      }
      */
      int[] permutation=Permutator.randomPermutation(Integer.parseInt(args[0]));
      for (int i=0; i<permutation.length; i++)
         System.out.print(permutation[i]+", ");
      System.out.println();
   }
}