原文链接 : https://blog.51cto.com/u_15067267/4403636?b=totalstatistic
求1~n的全排列，有两种方法，dfs和借助next_permutation()函数,这里我浅谈后者。
next_permutation（）原型是bool next_permutation(iterator start,iterator end），在c++库<algorithm>中，既找数组的下一个排列，这里的数组可以是整型、字符型等。
代码实现1~3的全排列:
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4 int main()
5 {
6 int num[3]={1,2,3};
7 do
8 {
9 cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
10 }while(next_permutation(num,num+3));
11 return 0;
12 }
括号内的范围类似sort函数，sort(首地址,首地址+个数),考虑升降幂的话加一个cmp函数来判断。
这样直接用很简单，但是我想讲一讲手写next_permutaion.
核心就是：如何找下一个排列，规律为何？
清楚一点：每次next_permutation确定的下一个排列实则只交换了两个数，如原来是1234，下一个为1243，交换了4和3.
如9237740这个排列，下一个是谁？如何做交换？
核心：从后往前找，找一对递增的相邻数，如40不是递增，74也不是，37是，记这对递增数的前一个数3为关键数，从后面找比它大的数中的最小数4，做交换变为7247730，再将4后面做一次颠倒得到7240377，即9237740的下一个全排列数。
换一种理解，我们从后找发现7740是逆序，无法通过交换得到一个比原数大的数，往前走，37740非逆序，将3和4交换，变为47730，做一次翻转，得到9237740，正好是9237740的下一个排列数。
看代码吧：
1 #include <iostream>
2 using namespace std;
3
4 const int N = 20;
5 int a[N];
6 int n;
7
8 void swap(int *a,int *b)
9 {
10 int t = *a;
11 *a = *b;
12 *b = t;
13 }
14
15 void reverse(int *a,int *b)
16 {
17 while (a<b) {
18 swap(a++,b--);
19 }
20 }
21
22 bool next_per()
23 {
24 int *end = a + 1 + n; // 尾指针
25 if (end == a + 1) return false; // n = 0
26 end--;
27 int *p,*pp,*find;
28 p = end;// p从后往前遍历
29 while (p != a + 1) {
30 pp = p; // pp为p右相邻指针
31 p--;
32 if (*p < *pp) {// 相邻递增
33 find = end; // 从后往前 找最小的大于*p的数 同时也是第一个大于*p 的数
34 while (*find <= *p) find--;
35
36 swap(p,find);// 交换
37 reverse(pp,end); // 翻转
38 return true;
39 }
40 }
41 return false;
42
43 }
44
45 int main()
46 {
47 cin>>n;
48 for (int i = 1; i <= n;i++) {
49 a[i] = i;// 初始化
50 }
51 do{
52 for (int i = 1; i <= n; i++)
53 cout<<a[i];
54 cout<<"\n";
55 }while(next_per());
56
57 return 0;
58 }
-----------------------------------
关于全排列--手写next_permutation()函数