今天学习并记录一下全排列问题。即给定一组序列，得到他们各个元素可以形成的所有排列组合序列。
如：1，2，3。 得到：1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1;
拿到问题先给出自己思考的结果
1.基于选择的全排列算法
算法思想：如上例，1，2，3. 第一个位置，可以有3种结果，1或2或3。在第一个位置选定后，第二个位置就只有剩下的两种结果。.....依次类推，最后一个位置只能填最后的一个结果。
从数学的角度上看，全排列一共有n!个结果，对应的算法时间复杂度也需要遍历n!种。根据这个数学的想法，我编写了如下程序。
/** 函数名称：全排列算法 描述：通过选择方法实现的全排列 参数：参数一：待排列数组，int型数组；参数二：数组长度，int型； 参数三：深度；参数四：int型数组,用于保存结果的临时数组，注意长度和待排列数组长度一致 返回值：void 渐进时间复杂度：O(pow(n,n)) 编写人：李一帆 **/ void permutationByChoose(int *data,int n,int length,int *tempData){ if(n==length){ listPrint(tempData,length); cout<<endl; }else{ for(int i=0;i<length;i++){ if(data[i]!=-1){ tempData[n]=data[i]; data[i]=-1; permutationByChoose(data,n+1,length,tempData); data[i]=tempData[n]; } } } }
在这个程序中，设置一个临时的数组作为排序结果的保存。每次递归填好一个数，每次递归的广度循环中，遍历每个待排列数组的元素，将标记为“未被使用（程序中为不为-1的元素）”，最终得到所有结果。
下来学习算法书上的全排列算法
2.基于交换的全排列算法。
算法思想：书中用到了前缀的概念，但实质和数学上和我的算法思想相同，都是依次排好每一位的数。不同的是，书中算法是基于交换的，相比我的算法，少了一个临时数组的内存空间。也具有了记忆性，
将我的算法的时间复杂度为O(pow(n,n))降低到了数学的下限O(n!)。它每次通过交换使得待排列数组的第一项得到不同结果，但它每次递归时，都会将数组长度减一，这样在每次的递归中，所需处理的数组长度
就会减少，可以降低遍历次数。最终直到剩下的数组长度为1时，即输出一种结果。
下面给出代码
/** 函数名称：全排列算法 描述：通过交换方法实现的全排列 参数：参数一：待排列数组，int型数组；参数二：起始下标，int型；参数三：结束下标，int型； 返回值：void 渐进时间复杂度：O(n!) 编写人：李一帆 **/ void permutationBySwap(int *data,int k,int m){ if(k==m){ listPrint(data,4); cout<<endl; }else{ for(int i=k;i<=m;i++){ swapData(&data[k],&data[i]); permutationBySwap(data,k+1,m); swapData(&data[k],&data[i]); } } }
算法讨论
1.以上两种算法都在具有相同元素时，最后结果都没有做去重。
2.书上算法比我思考的结果优越很多，直观上是时空复杂度的降低。还有一个问题是我思考的算法每次需要记录元素的状态为待使用，这就造成了一些问题和麻烦。
原文：https://www.cnblogs.com/fangexuxiehuihuang/p/14163453.html