package my;
import java.io.*;
import java.util.*;
class Ji{
public static void main(String args[])throws IOException 
{ System.out.println("請輸入一個整數：");
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s;
int n=0;
 while((s = (in.readLine()).trim())== null ||s.length()==0)
{ System.out.println("請輸入非空的字符串");
if(s.length()>=1) break;
}
System.out.print("你輸入的整數是:");
try
{ n=Integer.parseInt(s);
	
}
catch(Exception  e){
	System.out.println(e.toString());
	s=null;

}
System.out.println(n);
int []li=new int[n+1];
int []ji=new int[n+1];
li[0]=n;
for(int i=1;i<=n;i++)
   { System.out.println("請輸入第"+i+"個數字");
     in = new BufferedReader(new InputStreamReader(System.in));
     int m=0;
     while((s = (in.readLine()).trim())== null ||s.length()==0)
       { System.out.println("請輸入非空的字符串");
          if(s.length()>=1) break;
        }
    
     try
       { m=Integer.parseInt(s);
        }
    catch(Exception  e){
	        System.out.println(e.toString());
	      s=null;
	           }
    li[i]=m;

	}
	/////////////////
	
Date timeStart=new Date();//計時器

for(int k=1;k<=n-1;k++)
 { for(int a=1;a<n-k+1;a++)
     {if(li[a]>li[a+1])
     {
     	int temp=li[a];
     	li[a]=li[a+1];
     	li[a+1]=temp;
     }
      }
 }
 
   int zongNum=1;
 
for(int j=1;j<=n;j++)
   ji[j]=li[n-j+1];
   
//開始全排列
int index=-1;
int min=-1;
int flag=-1;
int minShu=-1;
int count=0;
Ji hh=new Ji();
	System.out.print("排列");
	for(int f=1;f<=n;f++)
   System.out.print(li[f]+" ");
    System.out.println();
text :while(true){
//	count++;
//if(count>=6) break;

 for(int x=n;x>=2;x--)
 { if(li[x]>li[x-1])
    { zongNum++; 
    index=x-1; 
      minShu=hh.minIndex(li,index,n);
     
      for(int u=1;u<=n;u++) 
           if(li[u]==minShu)  min=u;
     flag=li[index];
     li[index]=li[min];
     li[min]=flag;
  
  for(int b=index+1;b<n;b++)
  { for(int c=index+1;c<n;c++)
     {if(li[c]>li[c+1])
         {int ke=li[c];
              li[c]=li[c+1];
             li[c+1]=ke;
           }
     }
  }
  /////////
  
      break ;
    }
  }
  	System.out.print("排列");
	for(int f=1;f<=n;f++)
   System.out.print(li[f]+" ");
    System.out.println();
  int num=0;
  for(int v=1;v<=n;v++)
  { 
  if(li[v]==ji[v])
  {num++;
  }
  if(num==n)
    break text;
  }
 
}
Date timeEnd=new Date();
long time=timeEnd.getTime()-timeStart.getTime();
System.out.println(time);
System.out.println("耗時"+time/(1000*60*60)+"小時"+time%(1000*60*60)/(1000*60)+"分"+time%(1000*60)/1000+"秒"+time%1000+"毫秒");
 System.out.println("總的排列個數為"+zongNum);
}


public int minIndex(int []z,int index,int all)
{ 
int temp=z[all];
int init=z[index];
System.out.println();
for(int g=index+1;g<all;g++)
{
 for(int i=all;i>g;i--)
 {  if(z[i]<z[i-1])
 {temp=z[i];
 z[i]=z[i-1];
 z[i-1]=temp;
 }
}
 }
 for(int s=index+1;s<=all;s++)
 {if(z[s]>init){temp=z[s];break;
 }
 }
return temp;
}
}