一、全排列的概念
排列:
从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
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
如果觉得《全排列算法的理解与实现(递归+字典序)》对你有帮助,请点赞、收藏,并留下你的观点哦!