next_permutation用法

next_permutation就是按照字典序排列得到所有的排列组合！

例如

我们需要输出{ 1 , 2 , 3 , 4 } 的全排列（调用STL）

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int main()
 5 {
 6     int ans[4]={1,2,3,4};
 7     sort(ans,ans+4);    /* 这个sort可以不用，因为{1，2，3，4}已经排好序*/
 8     do                             /*注意这步，如果是while循环，则需要提前输出*/
 9     {
10         for(int i=0;i<4;++i)
11             cout<<ans[i]<<" ";
12         cout<<endl;
13     }while(next_permutation(ans,ans+4));
14     return 0;
15 }

自己写全排列函数：

 1 int A[maxn];
 2 void Next_permutation(int n,int a[],int cur) {
 3     if (cur == n) {
 4         for (int i=0;i<n;i++) {
 5             printf("%d ",A[i]);
 6         }
 7         printf("\n");
 8         return ;
 9     }
10     else {
11         for (int i=1;i<=n;i++) { // 这里就有点类似于排序了
12             int ok = 1;
13             for (int j=0;j<cur;j++) {
14                 if (A[j] == i)
15                     ok = 0;
16             }
17             if (ok) {
18                 A[cur] = i;
19                 Next_permutation(n,a,cur+1);
20             }
21         }
22     }
23 }
24 
25 int main() {
26     int a[5] = {4,3,2,1,5};
27     Next_permutation(5,a,0);
28     return 0;
29 }

对于序列P生成可重复的全排列：

 1 int A[maxn],P[maxn];
 2 void Next_permutation(int n,int p[],int a[],int cur) {
 3     if (cur == n) {
 4         for (int i=0;i<n;i++) {
 5             printf("%d ",A[i]);
 6         }
 7         printf("\n");
 8         return ;
 9     }
10     else {
11         for (int i=0;i<n;i++) {
12             if (!i || p[i] != p[i - 1]) {   // 重复的我们就不需要再递归了
13                 int c1 = 0, c2 = 0;
14                 for (int j = 0; j < cur; j++)
15                     if (A[j] == p[i])
16                         c1++;
17                 for (int j = 0; j < n; j++)
18                     if (p[j] == p[i])
19                         c2++;
20                 if (c2 > c1) {
21                     A[cur] = p[i];
22                     Next_permutation(n, P, A, cur + 1);
23                 }
24             }
25         }
26     }
27 }
28 
29 int main() {
30     for (int i=0;i<5;i++)
31         scanf("%d",&P[i]);
32     Next_permutation(5,P,A,0);
33     return 0;
34 }

算出序列的第n个排列（注意这里从0开始计数）

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int main()
 5 {
 6     int ans[7]={1,2,3,4,5,6,7};
 7     sort(ans,ans+7);  /* 同上可以不用sort */
 8     int n=0; 
 9     do                             //注意这步，如果是while循环，则需要提前输出
10     {
11         if(n == 1654)
12         {
13              for(int i=0;i<7;++i)
14             cout<<ans[i];
15             cout<<endl;
16             break;
17         }
18         n++;
19      }while(next_permutation(ans,ans+7));
20     return 0;
21 }