蓝桥杯Java：生成全排列的两种方式

如果数组内无重复元素，可使用交换法（即法一）生成全排列的情况，如果有重复元素，法一就会有重复情况，则利用抓取法来生成全排列的情况。

具体参看代码及注释

public class 全排列 {
    static int a[],b[],path[];
    static boolean visit[];
	public static void main(String args[]) {
	   a=new int [5];
	   for(int i=1;i<5;i++) {
		   a[i]=i;
	   }
	   System.out.println("无重复数字的全排列：");
	   pai(1);
	   System.out.println("有重复数字的全排列：");
	   b= new int[]{1,1,3,2};
	   visit=new boolean[b.length];
	   path=new int[b.length];
	   pai1(0,path);
	   
	  
   }
	//选取法生成全排列
	private static void pai1(int index, int[] path) {
		if(index==b.length) {
			for(int i=0;i<b.length;i++) {
				System.out.print(path[i]);
			}
			System.out.println();
			return;
		}
		for(int i=0;i<b.length;i++) {
			if(i>0&&!visit[i-1]&&b[i]==b[i-1]) continue;//若有两个相邻元素且值相等，若前一个元素未被访问到，则不生成这种排列
			if(!visit[i]) {
				visit[i]=true;
			    path[index]=b[i];
				pai1(index+1,path);
				visit[i]=false;
				
			}
		}
		
	}
	//全排列，这种方式是交换法，适用于没有重复数字的 数组
	private static void pai(int index) {
		if(index==4) {
			for(int j=1;j<4;j++) {
				System.out.print(a[j]);
			}
			System.out.println();
			return;
		}
		for(int k=index;k<4;k++) {
			{//交换两个元素的位置
			int te =a[index];
			a[index] =a[k];
			a[k]=te;
			}
			//这儿一定是index+1,而不是k+1;
			//递归发现更多的排列
			pai(index+1);
			
			{//递归之后需要回溯
				int te =a[index];
				a[index] =a[k];
				a[k]=te;
				}
		}	
	}
	
	 

}

代码运行截图：