当前位置: 代码迷 >> 综合 >> stl 之 next_permutation()
  详细解决方案

stl 之 next_permutation()

热度:1   发布时间:2023-12-26 10:01:33.0

组合数学中的全排列问题,有两个相关函数:

  • 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函数)