首页 > 代码库 > 生成排列算法
生成排列算法
1、递归方法
例如，如果集合是{1,2,3},那么这个集合中元素的所有排列是{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}，显然，给定n个元素共有n!种不同的排列，如果给定集合是{1,2,3,4}，可以用下面给出的简单算法产生其所有排列，即集合(1,2,3,4)的所有排列有下面的排列组成：
（1）以1开头后面跟着(2,3,4)的排列
（2）以2开头后面跟着(1,3,4)的排列
（3）以3开头后面跟着1,2,4)的排列
（4）以4开头后面跟着(1,2,3)的排列，这显然是一种递归的思路，于是我们得到了以下的实现：
void swap(int &a,int &b){ a = a ^ b; b = a ^ b; a = a ^ b;}void permutation(int* a,int k,int m) { int i,j; if(k == m) { for(i=0;i<m;++i) cout << a[i]; cout<<endl; } else { for(j=k;j<m;++j) { swap(&a[k],&a[j]); permutation(a,k+1,m); swap(&a[k],&a[j]); } }}
去掉重复符号的全排列：在交换之前可以先判断两个符号是否相同，不相同才交换，这个时候需要一个判断符号是否相同的函数。
void swap(int &a,int &b){ a = a ^ b; b = a ^ b; a = a ^ b;}bool isSwap(int *a ,int begin,int end){ for(int i=begin;i<end;++i) { if(a[i] == a[end]) return false; } return true;}void permutation(int* a,int k,int m) { int i,j; if(k == m) { for(i=0;i<m;++i) cout << a[i]; cout<<endl; } else { for(j=k;j<m;++j) { if(isSwap(a,k,j)) // 去掉重复元素 { swap(&a[k],&a[j]); permutation(a,k+1,m); swap(&a[k],&a[j]); } } }}
2、非递归实现
基本思想是:
1.对初始队列进行排序，找到所有排列中最小的一个排列Pmin。
2.找到刚刚好比Pmin大比其它都小的排列P(min+1)。
3.循环执行第二步,直到找到一个最大的排列,算法结束。
如排列ABCDE，这是所有排列中最小的一个排列，刚好比ABCDE大的排列是：ABCED。
算法如下：
给定已知序列P = A1A2A3.....An
对P按字典排序，得到P的一个最小排列Pmin = A1A2A3....An ，满足Ai > A(i-1) (1 < i <= n)
从Pmin开始,找到刚好比Pmin大的一个排列P(min+1)，再找到刚好比P(min+1)大的一个排列，如此重复。
1.从后向前（即从An->A1）,找到第一对为升序的相邻元素，即Ai < A(i+1)。
若找不到这样的Ai，说明已经找到最后一个全排列，可以返回了。
2.从后向前,找到第一个比Ai大的数Aj，交换Ai和Aj。
3.将排列中A(i+1)A(i+2)....An这个序列的数逆序倒置，即An.....A(i+2)A(i+1)。因为由前面第1、2可以得知，A(i+1)>=A(i+2)>=.....>=An,这为一个升序序列，应将该序列逆序倒置，所得到的新排列才刚刚好比上个排列大。
4.重复步骤1-3,直到返回。
void swap(int *a,int i,int j) { a[i]^=a[j]; a[j]^=a[i]; a[i]^=a[j]; } //将数组a中的下标i到下标j之间的所有元素逆序倒置 void reverse(int a[],int i,int j) { for(; i<j; ++i,--j) { swap(a,i,j); } } void print(int a[],int length) { for(int i=0; i<length; ++i) cout<<a[i]<<ends; cout<<endl; } //求取全排列,打印结果 void combination(int a[],int length) { if(length<2) return; bool end=false; while(true) { print(a,length); int i,j; //找到不符合趋势的元素的下标i for(i=length-2; i>=0; --i) { if(a[i]<a[i+1]) break; else if(i==0) return; } for(j=length-1; j>i; --j) { if(a[j]>a[i]) break; } swap(a,i,j); reverse(a,i+1,length-1); } }
生成排列算法