一、全排列的概念
排列：
从n个数中选取m（m<=n）个数按照一定的顺序进行排成一个列，叫作从n个元素中取m个元素的一个排列。不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数，称为排列数。
全排列：
从n个元素取出n个元素的一个排列，称为一个全排列。全排列的排列数公式为 n!
时间复杂度：
n个数的全排列有n!种，每一个排列都有n个数据，所以输出的时间复杂度为O(n*n!)，呈指数级，无法处理大型数据。
二、递归的全排列算法
算法思路：
假设我们要对1，2，3，4四个数进行全排列，过程如下：
(a)首先保持1不变，对2，3，4全排列；
(b)保持2不变，对3，4全排列；
(c)保持3不变，对4全排列，4的排列只有一种。得到1，2，3，4
(d)然后3不能不变了，继续保持2不变，3，4互换得到1，2，4，3
(e)以1，2打头的排列完成，接下来把3换到2的位置，继续(c)、(d)的操作
……
得到1，3，2，4
1，3，4，2
1，4，3，2
1，4，2，3
因此得到以1打头的全部排序，以此类推，得到以2，3，4打头的排序，得到全排序。
将以上过程总结成一个递归算法：
任取一个数打头，对后面n-1个数进行全排序，要求n-1个数的全排序，则要求n-2个数的全排序……直到要求的全排序只有一个数，找到出口。
伪代码：
m到n的全排序Permutation(m,n){if:全排列只有一个数，输出排列else: for{i=m;i<n;i++}{//i遍历第m~n个数，每次以a[i]所存的数值为打头的数swap(a[m],a[i]);//把要打头的数放到最开头的位置（即m所在的位置）Permutation(m+1,n);//递归swap(a[m],a[i]);//为避免重复排序，每个数打头结束后都恢复初始排序,防止重复的方法很多，不止这一种}}
从第m个元素到第n个元素的全排列代码：
void Permutation(int a[],int m,int n){if(m==n){cout<<a[0];for(int i=1;i<n;i++){cout<<" "<<a[i];}cout<<endl;}else {for(int i=m;i<n;i++){int temp=a[m];a[m]=a[i];a[i]=temp;Permutation(a,m+1,n);temp=a[m];a[m]=a[i];a[i]=temp;}}}
三、字典序
定义：对于一个序列a1,a2,a3,a4,a5....an的两个排列b1,b2,b3,b4,b5...bn和c1,c2,c3,c4,c5...cn, 如果它们的前k项一样，且c(k +1)> b(k+1),则称排列c位于排列b的后面。如1，2，3，4的字典序排在1，2，4，3的前面（k=2），1，3，2，4的字典序在1，2，3，4(k=1)的后面。
显然，对一个无重复元素的集合，它每种排序的字典序位置不同。按字典序进行全排列，使排列变得有序。
e.g.按字典序排列1，2，3的结果：
1，2，3
1，3，2
2，1，3
2，3，1
3，1，2
3，2，1
思路：
该算法的关键在于，找到紧跟在某一个排列后面的字典序。证明过程有点绕，我就讲讲我是如何通俗的理解这个算法的（举的例子可能不太严谨）。
假设有一排列，显然，若，则是它后面的字典序。
若，则需不断向前寻找，直到找到
我们可以看到，是降序排列，是排序中最大的情况（不理解的想象一下用1~9组成的各位不重复的最大数是987654321）。
想象有个十进制数19，我们来看一下要找到比它大的数——20，需要做哪些事情：由于个位数是9，已是最大情况，所以我们要将十位稍微调大一点，然后把个位改到最小，便得到紧跟着19后面的数。
因此，仿照上面的例子，我们做以下操作：从am+1,...,an中找到比am大的最小项，和am互换位置，然后再将新的am+1,...,an升序排列（将新的am+1,...,an改到最小，就如十位数20个位的0），这样得到的字典序便是紧挨着排列的后一个字典序。
字典序算法的实现：
bool Next_Permutation(int a[], int n){int i,m,temp;for(i = n-2;i >= 0;i--){if(a[i+1] > a[i]) break;}if(i < 0) return false;m = i;i++;for(;i<n;i++){if(a[i] <= a[m]){i--;break;}else if(i==n-1) break;}temp=a[m];a[m]=a[i];a[i]=temp;sort(a+m+1,a+n);cout<<a[0];for(int i=1;i<n;i++){cout<<" "<<a[i];}cout<<endl;return true;}void dict_Permutation(int a[],int n){sort(a,a+n);cout<<a[0];for(int i=1;i<n;i++){cout<<" "<<a[i];}cout<<endl;while(Next_Permutation(a,n));}
利用STL中的next_permutation()函数写全排列
C++的STL真是个令人偷懒的好东西。algorithm中提供了next_permutation模版函数，可直接代替上面的Next_Permutation（）函数，不过这个函数没有输出，而是直接把数组变成了它的下一个字典序。
利用STL求全排列代码：
void stl_Permutation(int a[],int n){int b[n];for(int i=0;i<n;i++){b[i]=a[i];}sort(b,b+n);do{cout<<b[0];for(int i=1;i<n;i++) cout<<" "<<b[i];cout<<endl;}while(next_permutation(b,b+n));}
比较：
在处理元素相同情况时，字典序算法不会重复输出。而一开始给出的递归算法会重复（要使之不重复，应在交换之前判断相邻着的两个数是否相同，如果相同，则不交换）。但是字典序算法把原来数组改变了，若需要保留原数组可以拷贝一个数组b，在新数组内操作。
作者：楠子小先生
链接：/p/50a27d7d2972
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
如果觉得《全排列算法的理解与实现（递归+字典序）》对你有帮助，请点赞、收藏，并留下你的观点哦！
