package com.dc.test;

import java.math.*;
import java.util.*;

public class Arrange{

	private int[] index;//用于存儲需要全排列的數組的下標的成員變量。
	private int n;//表示待排數組的元素個數。
	private long numLeft;//用于存儲剩余排列序列個數的成員變量。
	private long total;//用于存儲排列序列總數的成員變量。
	
	public Arrange(int n){
		this.n=n;
		reset();//調用重置
	}
	
	public void reset(){
		//初始化數組index。
		index=new int[n];
		for(int i = 0; i < index.length; i++){
			index[i] = i;
		}
		
		//初始化numLeft，開始時numLeft應該為n!.
		total=1;
		for(int i = n;i>1;i--){
			total*=i;
		}
		numLeft=total;
	}

	//判斷是否排序結束
	public boolean hasMore(){
		return numLeft > 0;
	}


	//得到下一個排列序列
	public int[] getNext(){

		if (numLeft==total){
			numLeft -=1;
			return index;
		}

		int j = index.length - 2;
		while (index[j] > index[j + 1]){
			j--;
		}

		int k = index.length - 1;
		while (index[j] > index[k]){
			k--;
		}
		
		int temp;
		temp = index[k];
		index[k] = index[j];
		index[j] = temp; 

		int r = index.length - 1;
		int s = j + 1;

		while (r > s){
			temp = index[s];
			index[s] = index[r];
			index[r] = temp;
			r--;
			s++;
		}

		numLeft-=1;
		return index;

	}


}