枚举排列

生成1~n 的排列

题目：输入整数n，按字典从小到大的顺序输出前n个数的所有排列。两个序列的大小关系等价于从头开始第一个不相同位置处的大小关系。

输入：

3

输出：

(1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)

code：

#include <stdio.h> int A[1001]; void print_permutation(int n,int *A,int cur){ int i,j; if(cur==n){ int flag=0; for(i=0;i<n;i++){ if(flag==0) printf("(%d ",A[i]); else if(flag==n-1) printf("%d)",A[i]); else printf("%d ",A[i]); flag++; } printf("\n"); } else for(i=1;i<=n;i++){ int ok=1; for(j=0;j<cur;j++) if(A[j]==i)ok=0; if(ok){ A[cur]=i; print_permutation(n,A,cur+1); } } } int main() { int n; scanf("%d",&n); print_permutation(n,A,0); return 0; }

生成可重集的排列

题目：如果把问题改成：输入数组P,bingan字典序数组A各元素的所有全排列。

输入：

3 1 2 3

输出：

(1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)

code：

#include <stdio.h> int P[1001],A[1001]; int print_permutation(int n,int *P,int *A,int cur){ int i,j; if(cur==n){ int flag=0; for(i=0;i<n;i++){ if(flag==0) printf("(%d ",A[i]); else if(flag==n-1) printf("%d)",A[i]); else printf("%d ",A[i]); flag++; } printf("\n"); } else for(i=1;i<=n;i++){ int ok=1; for(j=0;j<cur;j++) if(A[j]==P[i])ok=0;//修改 if(ok){ A[cur]=i; print_permutation(n,P,A,cur+1); } } } int main() { int n,t,i; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&P[i]); //对输入的数组进行排列 for(i=1;i<=n-1;i++){ if(P[i]>P[i+1]) {t=P[i];P[i]=P[i+1];P[i+1]=t;} } print_permutation(n,P,A,0); return 0; }

下一个排列

枚举所有排列的另一个方法是从字典最小排列开始，不停调用“求下一个排列”的过程。

输入：

3 1 2 3

输出：

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

排列生成器 按字典序的下一个排列 next_permutation()

code：

#include <stdio.h> #include<algorithm> using namespace std; /* algorithm意为"算法",是C++的标准模版库（STL）中最重要的头文件之一，提供了大量基于迭代器的非成员模版函数。 */ 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]); printf("\n"); }while(next_permutation(p,p+n));//求下一个排列 return 0; }