//=================================================================
// Name: class Permutations
// Author: Mike sun
// date:   05/05/2004
// a) This function implements dictionary-permutation algorithm
//    of the whole permutation of n numbers, 1,2 3,...,n
//
// b) parameters: a is any permutation of 1,2,...,n
// c) output: output all the permutations of 1,2,...,n
// d) The algorithm
//    for a given permutation a
//    1. find the maximun i such that a(i-1) < a(i), ie. find i=max(k: a(i-1) < a(i))
//    2. for the fixed i, find the maximum j such that a(i-1) < a(j), find j=max(k: a(i-1) < a(k))
//    3. swap a(i-1) with a(j), got new a(1),...,a(n)
//    4. in a(1),...,a(i-1), a(i),...,a(n), reverse a(i),...,a(n), got new a(1),...,a(n)
//    5. one loop of the steps 1,2,3,4 above will find the next permutation of the given a
//    6. all together there are n! permutations, and so use n! as the upper bound of the control loop
//
//
//=================================================================

import java.lang.Math;




 public class Permutations
 {
   private int permutations[][];
   private boolean isDecreasing=true;

   public Permutations()
   {}

   public int[][] findAllLexPermutations(int[] a)
   {
      int n=a.length;
      int k=1;
      int i=0;
      int j=1;

      int numPermutations = factorial(n);

      permutations=new int[numPermutations][n];

      //put the original line into the first line
      for (int q=0;q<n;q++)
      {
		  permutations[0][q]=a[q];
	  }

	  //----------------------------------------------
	  //test if the input a is monotonously decreasing
	  //then the boolean variable isDecreasing will be
	  //assigned value. If isDecreasing = true, then a[]
	  //is decreasing
	  //----------------------------------------------

	  testDecrease(a);

	  //-----------------------------------------------
	  // if the input a is decreasing, like 5 4 3 2 1
	  // then reverse it to 1 2 3 4 5 and load it into
	  // permutations[][]
	  //-----------------------------------------------
	  if ( isDecreasing == true )
	  {
	      a=reverse(a);
	      for (int q=0;q<n;q++)
		  {
		  	 permutations[1][q]=a[q];
	      }

	  }

      //-------------------------------------------------------
      // if a is not a decreasing array, then we start with p=1
      //-------------------------------------------------------
      if ( isDecreasing == false )
      {
      		for (int p=1;p<numPermutations; p++)
      		{
      			//--------------------------------------------------------------
      			// find the maximun i such that a(i-1) < a(i), ie. find
      			// i=max(k: a(k-1) < a(k)), i=1 if no k to satisfy a(k-1) < a(k),
      			//--------------------------------------------------------------
            	i=findMaxConsecutiveIncreaseIndex(a);

      			//--------------------------------------------------------------
     			// for the fixed i, find the maximum j such that a(i-1) < a(j),
     			// find j=max(k: a(i-1) < a(k)), if no such j, let j=1
      			//--------------------------------------------------------------
      			j=findMaxNonConsecutiveIndex(i, a);

      			//----------------------------------------------
     			// swap a(i-1) with a(j), got new a(1),...,a(n)
      			// if i=1, then don't swap
      			//----------------------------------------------
                a=swapTwoTerms(i, j, a);

      			//---------------------------------------------------------
      			// in a(1),...,a(i-1), a(i),...,a(n),reverse a(i),...,a(n),
      			// got new a(1),...,a(n) no reverse will happen if i=n
      			//---------------------------------------------------------
      			a=reverseRightHalf(i, a);

            	for (int y=0;y<n;y++)
            	{
            	    permutations[p][y]=a[y];
				}
     		}
      }
      else   // if a is a decreasing array, then we start with p=2
      {
      		for (int p=2;p<numPermutations; p++)
      		{
      			//--------------------------------------------------------------
				// find the maximun i such that a(i-1) < a(i), ie. find
				// i=max(k: a(k-1) < a(k)), i=1 if no k to satisfy a(k-1) < a(k),
      			//--------------------------------------------------------------
            	i=findMaxConsecutiveIncreaseIndex(a);


      			//--------------------------------------------------------------
				// for the fixed i, find the maximum j such that a(i-1) < a(j),
				// find j=max(k: a(i-1) < a(k)), if no such j, let j=1
				// 找使得a(i-1) < a(k)成立的最小的a(k)
      			//--------------------------------------------------------------
      			j=findMaxNonConsecutiveIndex(i, a);

      			//----------------------------------------------
     			// swap a(i-1) with a(j), got new a(1),...,a(n)
      			// if i=1, then don't swap
      			// 交換a(i-1) 和 a(j)
      			//----------------------------------------------
      			a=swapTwoTerms(i, j, a);

      			//---------------------------------------------------------
				// in a(1),...,a(i-1), a(i),...,a(n),reverse a(i),...,a(n),
				// got new a(1),...,a(n) no reverse will happen if i=n
				// 使得 a(i),...,a(n)反序
      			//---------------------------------------------------------
      			a=reverseRightHalf(i, a);

      			//將數組a的值賦給permutations
            	for (int y=0;y<n;y++)
            	{
            	    permutations[p][y]=a[y];
				}
     		}
      }
     return permutations;

 }

  public int factorial(int n)
  {
 	  int m=n;
 	  for (int k=n-1; k>0;k--)
 		   m=m*k;

 	  return m;
  }


  protected void testDecrease(int [] a)
  {
        for (int k=0;k<a.length-1;k++)
        {
  		    if (a[k] < a[k+1])
  		        isDecreasing = false;
	    }
  }


  protected int[] reverse(int[] a)
  {
	  int n=a.length;
	  int[] b= new int[n];

	  for (int k=0; k<n; k++)
	  {
		  b[k]=a[n-k-1];
	  }
	  return b;
   }


   protected int findMaxConsecutiveIncreaseIndex(int[] a )
   {
	     int count=0;
         for (int q=1;q<a.length;q++)      //yes
      	 {
        		if( a[q-1] < a[q] )      //%choose max i
            		count=q;
		 }
      	 return count; //%end choosing max i
   }


   protected int findMaxNonConsecutiveIndex(int i, int[] a)
   {
	    int count1=0;
		for (int m=1; m<a.length; m++)
      	{
        	if ( (i>0) && (a[i-1] < a[m])  )      //%choose max i
                	count1=m;
		}
		return count1;
   }

   protected int[] swapTwoTerms(int i, int j, int[] a)
   {
            if(i>0)
      		{
            		int q = a[i-1];
            		a[i-1] = a[j];
            		a[j] = q;
			}
	        return a;

   }

   protected int[] reverseRightHalf(int i, int[] a)
   {
	     int n=a.length;
         int b[];
      	 b=new int [n];


      	for (int m=i; m<n; m++)
      	     b[m]=a[n-m+i-1];

      	for (int m=i; m<n; m++)
      		a[m]=b[m];

	    return a;
   }




}