7.2.1 生成1~n的全排列
#include<stdio.h> int A[100]; // 输出1~n的全排列 void print_permutation(int n, int* A, int cur) { int i, j; if(cur == n) { // 递归边界 for(i = 0; i < n; i++) printf("%d ", A[i]); printf(" "); } else for(i = 1; i <= n; i++) { // 尝试在A[cur]中填各种整数i int ok = 1; for(j = 0; j < cur; j++) if(A[j] == i) ok = 0; // 如果i已经在A[0]~A[cur-1]出现过，则不能再选 if(ok) { A[cur] = i; print_permutation(n, A, cur+1); // 递归调用 } } } int main() { print_permutation(4, A, 0); return 0; }
生成0至 n-1的排列：
bool used[MAX_N]; int perm[MAX_N]; // 生成{0,1,2,3,4,...,n-1}的n!种排列 void permutation1(int pos, int n) { if (pos == n) { /* * 这里编写需要对perm进行的操作 */ return ; } // 针对perm的第pos个位置，究竟使用0~n-1中的哪一个进行循环 for (int i = 0; i < n; i++) { if (!used[i]) { perm[pos] = i; // i已经被使用了，所以把标志设置为true used[i] = true; permutation1(pos + 1, n); // 返回之后把标志复位 used[i] = false; } } return ; }
7.2.2 生成可重集的排列
思路：
1、统计已经输出的某个数的次数，如果少于这个数总共出现的次数，就可以选择这个数
2、由于P[i]数据相同，所以可能多次递归相同数据，所以需要把P[i]排序，并且在递归前判断是否和前面的数据P[i-1]是否相同。
#include<cstdio> #include<cstring> #include<iostream> #include<string> #include<algorithm> using namespace std; const int N=20; int P[N]; int A[N]; void perm(int n, int *A, int cur) { if(n==cur) { for(int i=0;i<n;i++) printf("%d ", A[i]); printf(" "); } else for(int i=0;i<n;i++) { int ok=1; for(int j=0;j<cur;j++) { if(A[j]==P[i]) { ok=0; break; } } if(ok) { A[cur]=P[i]; perm(n, A, cur+1); } } } //生成可重集的排列（错误的） void perm2(int n, int *A, int cur) { if(n==cur) { for(int i=0;i<n;i++) printf("%d ", A[i]); printf(" "); } else for(int i=0;i<n;i++) { int c1=0, c2=0; for(int j=0;j<cur;j++) if(A[j]==P[i]) c1++; for(int j=0;j<n;j++) if(P[j]==P[i]) c2++; if(c1<c2) { //printf("%d %d ", c1, c2); A[cur]=P[i]; perm2(n, A, cur+1); } } } //生成可重集的排列（修正后） // P 需要排序过 // 输出数组P中元素的全排列。数组P中可能有重复元素 void perm3(int n, int *A, int cur) { if(n==cur) { for(int i=0;i<n;i++) printf("%d ", A[i]); printf(" "); } else for(int i=0;i<n;i++) if(!i || P[i]!=P[i-1]) { int c1=0, c2=0; for(int j=0;j<cur;j++) if(A[j]==P[i]) c1++; for(int j=0;j<n;j++) if(P[j]==P[i]) c2++; if(c1<c2) { //printf("%d %d ", c1, c2); A[cur]=P[i]; perm3(n, A, cur+1); } } } int main() { int n; cin>>n; for(int i=0;i<n;i++) cin>>P[i]; printf("perm "); perm(n, A, 0); printf("perm2 "); perm2(n, A, 0); printf("perm3 "); perm3(n, A, 0); return 0; }
7.2.3 解答树
一次生成一个解答元素
每个叶子对应一个排列，共有n!个叶子。 共有e*n!个节点。
最后一层叶子n!个，倒数第二层也是n!个，所以上面各层总共加起来也不到n!个。
就是排列树啦！！
3个元素情况如上，叶子有3!=6, 倒数第二层也是3!=6个。
7.2.4 下一个排列
用stl的next_permutation
注意，return false时有回到最小序列
#include<cstdio> #include<algorithm> using namespace std; /* 函数实现原理如下： 在当前序列中，从尾端往前寻找两个相邻元素，前一个记为*i，后一个记为*ii，并且满足*i < *ii。然后再从尾端寻找另一个元素*j，如果满足*i < *j，即将第i个元素与第j个元素对调，并将第ii个元素之后（包括ii）的所有元素颠倒排序，即求出下一个序列了。 */ bool next_perm(int *first, int *last) { //空区间 if(first==last) return false; int *i=first; //只有一个 if(++i==last) return false; i=last; --i; while(1) { int *ii=i; --i; //锁定两个相邻元素 if(*i<*ii) {//如果前一个比后一个小 int *j=last; while(!(*i<*--j));//从尾向前找,直到找到一个比*i大的元素 printf("swap %d %d ", *i, *j); iter_swap(i, j);//交换i,j reverse(ii, last);//将从ii开始之后的元素逆序重排 return true; } if(i==first)//到最前面了,没有更大的序列了 { reverse(first, last);//全部逆序排列,变成最小的序列 return false; } } } int main() { int n, p[10]; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &p[i]); sort(p, p+n); // 排序，得到p的最小排列 do { for(int i = 0; i < n; i++) printf("%d ", p[i]); // 输出排列p printf(" "); //} while(next_permutation(p, p+n)); // 求下一个排列 } while(next_perm(p, p+n)); // 求下一个排列 //最后会输出最小序列 for(int i = 0; i < n; i++) printf("%d ", p[i]); // 输出排列p return 0; }