next_permutation() 全排列函数_综合

排列（Arrangement），简单讲是从 $N$ 个不同元素中取出 $M$ 个，按照一定顺序排成一列，通常用 $A (M, N)$ 表示。当 $M = N$ 时，称为全排列（Permutation）。
从数学角度讲，全排列的个数 $A (N, N) = (N) ? (N ? 1) ? . . . ? 2 ? 1 = N!$ ，但从编程角度，如何获取所有排列？那么就必须按照某种顺序逐个获得下一个排列，通常按照升序顺序（字典序）获得下一个排列。

例如对于一个集合 $A =$ { $1, 2, 3$ }，首先获取全排列 $a 1 : 1, 2, 3$ ；然后获取下一个排列 $a 2 : 1, 3, 2$ ；按此顺序， $A$ 的全排列如下：

$a 1 : 1, 2, 3$ ;　　 $a 2 : 1, 3, 2;$ 　　 $a 3 : 2, 1, 3$ ;　　 $a 4 : 2, 3, 1$ ;　　 $a 5 : 3, 1, 2$ ;　　 $a 6 : 3, 2, 1$ ;　　共 $6$ 种。

    那么我们有时就需要求下一种全排列，在STL中的algorithm已经给出了一种健壮、高效的方法，即 next_permutation(int *begin, int *end)
    注意，这个函数是直接将传递的数组转换成了下一个全排列数组，并且有一个返回值。
    当返回为 $1$ 时，表示找到了下一全排列；返回 $0$ 时，表示无下一全排列。注意，如果从begin到end为降序，则表明全排列结束，逆置使其还原到升序

因而我们可以用这个返回值求得所有的全排列

同时，相对应的，上一个排列即为prev_permutation(int *begin, int *end)

#include<bits/stdc++.h>
using namespace std;int main() {char a[3]= {'a','b','c'}; //第一个排列保证正序，有时候根据题目要求，需要对其进行排序处理。for(int i=1; i<=6; i++) { //i为总共排列的个数  ，及 3！for(int j=0; j<3; j++)printf("%c ", a[j]);printf("\n");next_permutation(a, a+3);//放在第一个排列的后边，输出第一个排列的下一个排列}printf("*******************\n");int b[4]= {0,1,2,3};do{for(int i=0; i<4; printf("%d ", b[i++]));printf("\n");} while(next_permutation(b, b+4));printf("*******************\n");int c[3]={3,2,1};next_permutation(c, c+3);for(int i=0; i<3; printf("%d ", c[i++]));
}