组合数学中的全排列问题,有两个相关函数:
- next_permutation(start, end) 当前排列的下一个(字典序)排列
- prev_permutation(start, end) 当前排列的上一个排列
上一个/下一个:对序列 {a, b, c},每一个元素都比后面的小,按照字典序列,固定a之后,a比bc都小,c比b大,它的下一个序列即为{a, c, b},而{a, c, b}的上一个序列即为{a, b, c},同理可以推出所有的六个序列为:{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a},其中{a, b, c}没有上一个元素,{c, b, a}没有下一个元素。
1. 返回值:true / false
2. 头文件:#include<slgorithm>
3. 代码:
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{int a[4]={1,2,3};do{for(int i=0;i<3;i++)cout<<a[i]<<",";cout<<endl;}while(next_permutation(a,a+3));return 0;
}
4. next_permutation(a,a+n):对数组的前n个元素进行全排列,并且会改变a数组的值。这也是下一句为什么要排序。
5. 注意:在使用该函数之前,要先对数组进行升序排列,不然输出的全排列数只是这个未排序的序列之后的。
6. next_permutation(node,node+n,cmp)也可以对结构体num按照自定义的排序方式cmp进行排序。
7. 相关例题:zcmu--1620: 全排列(dfs或next_permutation函数)