/**
 *@auther 皇阿玛
 *2019/9/16 13:51
 */

package courseOne;

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;


class Permutation{//递归方法，要找一个非递归的方法
	int total;
	static int count=0;
//	private int[] people;
	public Permutation(){}
	public Permutation(int total,int SelectPeople){
//		this.people = new int[SelectPeople];
		this.total = total;
	}
	public boolean next(List<Integer> lis,int start){
		if(start >= lis.size() ){
			System.out.println(lis);
			count++;
			return true;
		}
		for(int i=1;i<=total;i++){
			if( !lis.contains(i) ){
				lis.set(start, i);
			}else{
				continue;
			}
			next(lis,start+1);
			lis.set(start, -1);
		}
		return true;
	}
	public boolean next2(List<Integer> lis){//非递归写出来
		int flag = 0;//用来判断初始list是否全为0，则需要赋初值1，2，3...
		int ChangeFlag = 0;//用来判断是否已经对list进行更新了，若已更新，则直接退出并返回true
		for(int i=0;i<lis.size();i++){
			flag += lis.get(i);
		}
		if(flag == 0){//初始化
			for(int j=0;j<lis.size();j++){
				lis.set(j, j); //lis.set(index, element)
			}
			ChangeFlag = 1;
		}else{
			for(int k=lis.size()-1;k>=0;k--){
//				System.out.println("1.k = "+k);/////////////////////////////
				if(!IsMaxOrNot(lis,k) && ChangeFlag == 0){//最后一位不是最大值的话，就进行最小增值
					if( LittleIncrease(lis,k) )
						ChangeFlag = 1;
					//break;
					//若最后一位是最大值，则  k 进入下一层for循环，即把lis中的搜索位置前移
					//若更新的位置k不是最后一位，则需要对k位之后的数据进行从小到大更新！
					if(1 == ChangeFlag ){//如果最小更新的元素位置是k的话=>&& k < lis.size()
//						System.out.println("I'm complemening!!!,k = "+k+" lis = "+lis);
						Complement(lis,k);//对k之后的元素进行按顺序补全
					}
					break;
				}	
			}
		}
		if(1 == ChangeFlag)
			return true;
		else
			return false;
	}
	
	public boolean IsMaxOrNot(List<Integer> lis,int loc){//loc从0开始计数
		int[] tem = new int[total];//初值为0；
		Arrays.fill(tem, 0);	    //对数组用某个数进行填充
		int flag = 1;				//判断标志，默认是最大值，则flag=1，若不是最大值，则令flag=0;
		
		for(int i=0;i<lis.size() && i<loc;i++){//对loc之前&&已用过的 元素进行标记
			tem[lis.get(i)] = 1;
		}
		for(int j=0;j<total;j++){  //未用过的元素中去比较查找是否有更大的元素
			if(tem[j] != 1 && j>lis.get(loc))//数值 j 没用过，而且 j 比lis第loc位的数值要大。
				flag = 0;		   //说明list.get(loc)不是最大值，还有更大的数值可选
		}
		if(0==flag) 
			return false;
		else
			return true;
	}
	public boolean LittleIncrease(List<Integer> lis,int loc){//当某个位置的数值不是最大值时，进行最小限度地增加
		int[] tem = new int[total];//初值为0；
		Arrays.fill(tem, 0);	    //对数组用某个数进行填充
		int flag = 0;				//判断标志，默认是最大值，则flag=1，若不是最大值，则令flag=0;
		
		for(int i=0;i<lis.size() && i<loc;i++){//对loc之前&&已用过的 元素进行标记
			tem[lis.get(i)] = 1;
		}
		for(int j=0;j<total;j++){  //未用过的元素中去比较查找是否有更大的元素
//			System.out.println("2.lis.get(loc) = "+lis.get(loc)+" loc = "+loc);
			if(tem[j] != 1 && j>lis.get(loc)){//数值 j 没用过，而且 j 比lis第loc位的数值要大。
				lis.set(loc, j);   //把loc位置的数值增加为j;！！！！！！！！！！！！
				flag = 1;		   //完成增值工作
//				System.out.println("3.list = "+lis);
				break;
			}
		}
		if(0==flag){
//			System.out.println("false");
			return false;
		}
			
		else{
//			System.out.println("true");
			return true;
		}
			
	}
	public boolean Complement(List<Integer> lis,int loc){//loc是中间更新的位置下标(index) <=> k
		//当处理完的最小增值位置不是在最后一位时，需要对 后面 元素进行补全，按照剩余元素，从小到大处理;当前的 loc 位置  不用改动 ！！！！！
		int[] tem = new int[total];//初值为0；
		Arrays.fill(tem, 0);	    //对数组用某个数进行填充
		//int flag = 1;				//判断标志，
//		System.out.println("4.in Complement,loc = "+loc+", lis = "+lis);
		for(int i=0;i<=loc;i++){//对loc之前&&已用过的 元素进行标记(loc就是下标，直接带入index)  :i<lis.size() && 
			tem[lis.get(i)] = 1;				//这里loc要记得取等号
		}
		
		for(int j=loc+1;j<lis.size();j++){//j：每个待修正的位置坐标！！！对loc之后的元素进行重新洗牌，坐标从(loc+1)开始走
			int ChangeFlag = 0;//修补过程，已进行到的 位置 下标！！！
			for(int k=0;k<total && ChangeFlag == 0;k++){
				if(tem[k]!=1){
					lis.set(j, k);
					ChangeFlag = 1;
					//ChangeFlag++;
					tem[k] = 1;
//					System.out.println("5.lis = "+lis+", k = "+k+", loc = "+loc+", Changeflag="+ChangeFlag);
				}
			}
		}
		return true;
	}
	
}


public class PermutationExample {
	public static void main(String[] args){
		
		int sum = 0;
		int total = 5;
		int need = 3;// n <=> SelectPeople
		List<Integer> lis = new ArrayList<Integer>();
		List<String> lis2 = new ArrayList<String>();
//		lis2.add("q");
//		lis2.get(0);
//		System.out.println("ss");
		for(int i = 0 ; i < need;i++) {
			lis.add(0);
		}
		Permutation perm = new Permutation(total,need);
		
		
		while(perm.next2(lis)){
			System.out.println(lis);
			sum++;
		}
		System.out.println("The num of permutations is "+sum+" !!!");
//		while(sum>0){
//			perm.next2(lis);
//			System.out.println(lis);
//			sum--;
//		}
	}
}
		/**
		 * 
		 
		List<Integer> lis = new ArrayList<Integer>();
		for(int i = 0 ; i < need;i++) {
			lis.add(-1);
		}
		
		Permutation per = new Permutation(total,need);
		per.next(lis, 0);
//		int sum = 60;
//		while( sum>0 ){
//			per.next(lis, 0);
//			System.out.println(lis);
//			sum--;
//		}
		System.out.println("all of the number:"+per.count); 
		*/