一直都不太理解递归，这次写全排列的时候找到一张图最为简单的解释了“固定-交换”求全排列的原理。
全排列原理
【ABC】按照当前顺序存在一个列表里面，我们来看一下结构：
第一层--- A和A自己换位，固定0位置的A；A和B换位，固定0位置的B；A和C换位置，固定0位置的C；
第二层第一子部分--- (0位A已经被固定)【ABC】从1位开始，B和B自己换位，固定1位置的B；(0位A已经被固定)【ABC】从1位开始，B和C换位，固定1位置的C；//输出ABC
第三层第二子部分--- (0位A已经被固定) (1位C已经被固定)【ABC】从2位开始，B和B自己换位，固定3位置的B；//输出ACB
可以看到，递归的入口在【换位】之后，被换到首位的元素将被固定，新的首位将会++，换位后再次被固定。
递归出口在，当首位编号和列表长度已经一样的时候。
下面为了方便理解，直接显式的给出了起始位置为0，结束位置为2。(对于【ABC】这样一个length为3的列表)；
public static void main(String[] args){
int[] array = new int[]{1,2,3};
permute(array, 0,2);//input array; start position; end position
}
public static void permute(int[] given, int start, int end){
if(start == end){//如果起始位子已经等于结束位置了，则打印当前列表结束当前递归方法
for(int j : given){//for循环 按顺序打印当前列表
System.out.print(j);
}
System.out.println(" ");
}
else{//如果起始位置不等于结束位，则
for(int i=start; i<=end ; i++){//从起始位置开始
swap(given,i,start);//1.把当前位和起始位元素进行换位
//得到的新given数列为下一层递归的输入
permute(given,start+1,end);//进入下一层递归。
//换位以后的新given为输入数列，
//起始位置++(因为首位已经被固定住了)，
//结束位置不变
swap(given,start,i);//递归的重点在于结束低一层回到上一层时
//当层的given数列要和进入下层递归前保持一致
//在执行上一句进入下层递归之前我们交换了元素
//所以在上一句进入下层递归之后
//我们需要把交换了的元素换回原样
}
}
}
public static void swap(int[] array, int s, int i){
int t = array[s];
array[s] = array[i];
array[i] = t;
}
写一下得到【BCA】这个结果的递归流程：
1|拿到原始输入【ABC】，起始位为0
2|for( 起位(0) to 结束位){
3|swap: 将起位(0)和1位交换得到【BAC】
4|---->permute: 进入下层递归，输入为【BAC】，新起始位为1
5|swap: 下层递归结束，将元素归位，当前given回到【ABC】
6|}
7|---->
1|----拿到输入【BAC】，起始位为1
2|----for(起始位(0) to 结束位){
3|----swap: 将起位(1)和2位交换得到【BCA】
4|----|---->permute: 进入下层递归，输入为【BCA】，新起始位为2
5|----|swap: 下层递归结束，将元素归位，当前given回到【BAC】
6|----|}
7|----|---->
1|----|----拿到输入【BCA】，新起始位为2
2|----|----起始位=结束位，结束当层递归，回到上一层。
网友评论