1.不含重复元素
算法思路：
1、n个元素全排列 = （n-1）个元素的全排列+（另一个元素作为前缀）
2、出口：如果只有一个元素的全排列，则说明已经排完，输出数组；
3、不断将每个元素放在第一个元素，然后将这个元素作为前缀，并将其余元素继续全排列，等到出口，出口出去之后还需要还原数组。
#include <iostream> #include <malloc.h> #define maxSize 20 #define INF 1000 using namespace std; void swap_(char &a,char &b){ char temp; temp=a; a=b; b=temp; } void perm(char x[],int k,int m){ if(k==m){ for(int i=0;i<=m;++i) cout<<x[i]; cout<<endl; } else{ for(int i=k;i<=m;++i){ swap_(x[i],x[k]); perm(x,k+1,m); swap_(x[i],x[k]); } } } int main(int argc, char** argv) { char x[4]={'1','2','3','4'}; perm(x,0,3); return 0; }
2.含重复元素
算法思路：
因为排序是前缀加后缀，所以保证前缀每次不一样，才能行，也就是交换后不能重复，所有在交换前要检查 ；
只要从start开始到end（不包括end包括start）中间的元素与end元素相等，那么前缀就有可能相同，所以去掉。
比如：对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。
去掉重复规则：去重的全排列就是与当前头元素i交换的元素j不能与i~j之间的元素一样，这样才能保证前缀不一样！！！
bool IsSwap(vector<int>&a, int start, int end) { for(int i = start; i<end; i++) if(a[i] == a[end]) return false; return true; } void swap(vector<int>&a, int i, int j) { int temp; temp = a[j]; a[j] = a[i]; a[i] = temp; } void de_prem(vector<int>&a, int start, int end, vector<vector<int>>&ret) { //ret中存放的是所有排列的情况 if(start == end) { vector<int>::iterator iter; for(iter=a.begin(); iter<a.end(); iter++) { cout << (*iter) << " "; } cout<<endl; ret.push_back(a); return ; } else { for(int i = start; i <= end; i++) { if(IsSwap(a, start, i)) { swap(a, start, i); de_prem(a, start+1, end, ret); //每次选择子后一个元素为开始第一个元素 swap(a, i, start); } } } }
