next_permutation函数用法

阅读本书更多章节>>>>

做题时，有时候会碰到需要列举一些数字所有排列方式的情况。这时候大家恐怕会无从下手，但如果使用next_permutation函数，就简单了。next_permutation函数在头文件<algorithm>中，作用是是生成给定序列的下一个较大排序，直到序列按降序排列为止。到这里还需要强调的一点是，如果你希望生成所有的排列方式，一定要先将序列按升序排列，这里可以与sort函数结合起来使用，先用sort升序排列，再调用next_permutation函数。

具体怎么用，我们先看一个简单的示例：

# include <iostream># include <algorithm>using namespace std;int main(){int a[] = { 3,1,2 };sort(a, a + 3); //默认升序排列do {for (int i = 0; i < 3; i++) {cout << a[i] << " ";}cout << endl;} while (next_permutation(a, a + 3)); //第一个参数对应数组首，第二个参数对应数组尾return 0;}

运行结果：

1 2 31 3 22 1 32 3 13 1 23 2 1

这里是列举出1，2，3的所有排列情况。有人可能要问了，为什么要使用do~while，而不直接用while语句呢？因为我们希望生成的是所有排列方式，直接用while+next_permutation函数，会跳过1，2，3这种最开始的排列情况。

 下面，我们再来看一个具体的题目：

洛谷：[NOIP1998 普及组] 三连击

## 题目背景

本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。

## 题目描述

将 1, 2, ······ , 9 共9个数分成 3 组，分别组成 3 个三位数，且使这 3 个三位数构成 1 : 2 : 3 的比例，试求出所有满足条件的 3 个三位数。

##输入格式

无

## 输出格式

若干行，每行 3 个数字。按照每行第 1 个数字升序排列。

这里我们要把9个数划分为3段，每一段表示一个数。我们要找出所有可能的情况，就要列举出1~9的所有排列情况。直接应用next_permutation函数可大大降低题目的复杂度。

我的代码如下：

# include <iostream># include <algorithm>using namespace std;int main(){int a[] = { 1,2,3,4,5,6,7,8,9 }; //按升序排列int x1, x2, x3;do {x1 = 100 * a[0] + 10 * a[1] + a[2];x2 = 100 * a[3] + 10 * a[4] + a[5];x3 = 100 * a[6] + 10 * a[7] + a[8];if (x2 == 2 * x1 && x3 == 3 * x1) { //判断是否满足3:2:1cout << x1 << " " << x2 << " " << x3 << endl;}} while (next_permutation(a, a + 9));return 0;}

运行结果：

192 384 576219 438 657273 546 819327 654 981

以上是我的学习经验，next_permutation函数还可以对字母进行排序，但实际做题中几乎用不到，这里就不多讲了。很高心能与大家分享。

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-03-30/150874.html，文章来源：网络cs，作者：纳雷武，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！