每天一道算法题：打印n个元素的全排列

小鱼儿 2022-10-28 10:11 180阅读 0赞

## 1、回顾 ##

在前一篇文章[n个球中取出m个球][n_m]中介绍过组合与排列，如果是需要计算n个元素的全排列个数，那么我们只需要通过A(n,n)就能得到结果，但是我们需要将其打印出来，那应该要怎么做呢？

## 2、打印n个元素的全排列 ##

*  **递归思路分析**：首先，n个元素的全排列是什么？我们再写程序之前必须先搞清楚题目的意思，假设我们有3个元素【ABC】，那么，它的全排列就是：`【ABC】【ACB】【BAC】【BCA】【CAB】【CBA】`
 *  现在我们需要去想办法构造相似性，创造递归条件。在这里，我的想法是，从第一个元素开始，让它和后面的每一个元素进行位置交换（包括自己），交换了位置之后递归给下一个元素也就是从第二个元素开始，继续与后面的每一个元素进行交换，直到到循环末尾，对当前交换后的元素进行打印，因为是递归，每一层的元素会被使用多次，所以我们再每次打印之后还要让其还原到之前的位置，这里我主要是使用了回溯的思想，让其再交换一遍，就能还原了，下面我们来写代码帮助理解：

public static void printfArranager(char[] data,int k){ 
    		if(k==data.length){ 
    			for(int i=0;i<data.length;i++)
    				System.out.print(data[i]+" ");
    			System.out.println();
    		}
    		//从第一个元素开始，不断与后面的元素进行交换
    		for(int i=k;i<data.length;i++){ 
    			{ char t=data[k]; data[k] = data[i]; data[i] = t;}
    			//交换之后，将得到的新arr递归到【第二层】的函数，并让k+1，从第二个元素开始交换
    			printfArranager(data,k+1);
    			//交换之后需要进行回溯，如果不进行回溯，那么上面改变的arr会对本次循环之后的其他循环的交换造成影响
    			{ char t=data[k]; data[k] = data[i]; data[i] = t;}
    		}
    	}

**测试代码：**

public static void main(String[] args) {
            char data[] = "ABC".toCharArray();
            printfArrange1(data,0);
        }

**执行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]

为了能更好的帮助理解代码，下面我们来画一下的递归的内存分布图（为了便于观察递归，主要就画一下栈区的结构了）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70 1]  
结合上面的图，我们再分析一下printfArranager的栈区数据的变化：

//程序执行，main函数入栈，传入参数，第一次执行printfArrangel,printf函数入栈
    按顺序，整个执行流程如下：
    第一层： arr ：ABC k = 0 ； i=k,
    
    第一层第一次循环： arr[0]与arr[0]进行交换，结果不变。arr:ABC,递归下一层
    
    第二层： arr：ABC k = 1；i=k
    
    第二层第一次循环：arr[1]与arr[1]进行交换，结果不变，arr:ABC,递归下一层
    
    第三层： arr：ABC k = 2，i=k
    
    第三层：循环条件i<arr.length不成立，不执行后面的程序，故递归到此结束，根据
    判断打印当前所有元素ABC之后开始回调，回到第二层的第一次循环调用printf函数
    的后面，进行回溯操作，将当前循环的元素还原，以便第二次循环使用，到此，第二
    层第一次循环结束，开始第二次循环
    
    第二层第二次循环 arr:ABC k=1,i=k+1(原有的条件保持不变，之所以要回溯就是因
    为要保证不同层之间的数据相互不影响)，arr[k]与arr[i+1]进行交换，交换之后
    arr:ACB,递归到下一层
    
    第三层：循环条件i<arr.length不成立，不执行后面的程序，故递归到
    此结束，根据判断打印当前所有元素ACB之后开始回调，回到第二层的第二次循环调
    用printf函数的后面，进行回溯操作，到此，第二层第二次循环结束，开始第三次循
    环
    
    第二层第三次循环：arr:ABC k = 1,i=k+2,因为i超过了arr的界限，所以第二层的
    递归也到此结束，继续回到第一层的第一次循环的printf函数后面，进行回溯，进入
    第一层第二次循环
    
    第一层第二次循环：arr：ABC k = 0;i=k+1,arr[0]与arr[1]交换位置，交换之后
    arr:BAC,递归到下一层的新的循环
    
    第二层第一次循环：arr:BAC,k=1,i=k,arr[1]与arr[1]交换位置，交换之后，arr:
    BAC,递归到下一层的新的循环
    
    第三层：arr:BAC k=i=2,循环条件i<arr.length不成立，不执行后面的
    程序，故递归到此结束，根据判断打印当前所有元素BAC之后开始回调，回到第二层
    的第二次循环调用
    
    第二层第二次循环：arr:BAC,k=1,i=2,arr[1]与arr[2]交换位置，arr:BCA,递归到下一层。
    
    第三层：arr:BCA,i<arr.length循环条件不成立,结束递归，打印BCA之后回到第二层第二次循环执行回溯，因为i=2,所以第二层的循环也结束，回第一层
    
    第一层第三次循环：arr:ABC k=0,i=2,arr[0]与arr[2]进行交换，arr:CBA,交换之后，又开始递归
    
    ......就是一个循环的过程，写了两个过程了，第三也是一模一样的，就不写了，实
    在是写不动了emmm

以上就是递归的思路分析及内存的执行机制，**如果还有其他思路的大佬请务必分享给我，非常感谢！！！**

[n_m]: https://blog.csdn.net/qq_47953855/article/details/113697011
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]: /images/20221024/d7cb5f421ed641b1b9fc076ed83dfa82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70 1]: /images/20221024/9a7ee14bf9fc4ff995bd9d3f232a58f9.png