C++中的next_permutation全排列函数

什么是全排列

全排列是指从一组元素中按照一定顺序(按字典序排列）取出所有元素进行排列的所有可能情况。
例如，对于集合{1,2,3}，它的全排列包括：

• 1,2,3
• 1,3,2
• 2,1,3
• 2,3,1
• 3,1,2
• 3,2,1

C++标准库中的<algorithm>头文件提供了next_permutation函数，可以方便地生成序列的下一个排列。

用法

next_permutation(开始，结束)
输出所有比当前排列大的排列，顺序是从小到大
如何传入？
以数组a[5]={1,2,3,4,5}为例
next_permutation(a,a+5);
以vectorv为例
next_permutation(v.begin(),v.end());

在一些题目中，经常结合do while来用。

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;int main() {vector<int> v = {1, 2, 3};// 先排序以确保获得所有排列sort(v.begin(), v.end());do {for (int num : v) {cout << num << " ";}cout << "\n";} while (next_permutation(v.begin(), v.end()));return 0;
}

实现原理

next_permutation函数按照字典序生成下一个排列，其算法步骤如下：

从后向前查找第一个相邻元素对(i, i+1)，满足a[i] < a[i+1]

如果找不到这样的元素对，说明已经是最后一个排列，返回false

从后向前查找第一个大于a[i]的元素a[j]

交换a[i]和a[j]

反转i+1到末尾的所有元素

自定义比较函数

next_permutation也支持自定义比较函数，这在处理自定义类型或需要特殊排序规则时非常有用。

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;bool cmp(int a, int b) {return a > b; // 降序排列
}int main() {vector<int> v = {3, 2, 1};do {for (int num : v) {cout << num << " ";}cout << "\n";} while (next_permutation(v.begin(), v.end(), cmp));return 0;
}

注意事项

初始序列需要排序：为了获得所有可能的排列，初始序列应该是有序的（通常是升序）

修改原序列：next_permutation会直接修改传入的序列

返回值：当没有下一个排列时返回false，否则返回true

时间复杂度：O(n)，其中n是序列长度

相关题目

1.A+B Problem

题目来源：A+B Problem

解题思路：由于这里的n比较小，可以直接输出每种情况，但我们今天学习了全排列函数，就要运用它来高效实现。我们可以定义一个数组粗存1~n的值，再定义一个字符令它为’A’，这样对数组进行全排列，每次排列后的顺序加上这个字符，输出就是排列后的新字符。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[5];
signed main()
{int n,num=0;cin>>n;char s='A';for(int i=1;i<=n;i++)a[i]=i;do{for(int i=1;i<=n;i++){printf("%c",s+a[i]-1);if(i!=n)cout<<"+";}cout<<" Problem"<<endl;}while(next_permutation(a+1,a+1+n));return 0;
}

2.P1088 火星人

题目来源：P1088 [NOIP 2004 普及组] 火星人
** 题目描述**

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 $1,2,3,\cdots$。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为 $1,2,3,4$ 和 $5$，当它们按正常顺序排列时，形成了 $5$ 位数 $12345$，当你交换无名指和小指的位置时，会形成 $5$ 位数 $12354$，当你把五个手指的顺序完全颠倒时，会形成 $54321$，在所有能够形成的 $120$ 个 $5$ 位数中，$12345$ 最小，它表示 $1$；$12354$ 第二小，它表示 $2$；$54321$ 最大，它表示 $120$。下表展示了只有 $3$ 根手指时能够形成的 $6$ 个 $3$ 位数和它们代表的数字：

三进制数	代表的数字
$123$	$1$
$132$	$2$
$213$	$3$
$231$	$4$
$312$	$5$
$321$	$6$

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

== 输入格式==

共三行。
第一行一个正整数 $N$，表示火星人手指的数目（$1\le N\le 10000$）。
第二行是一个正整数 $M$，表示要加上去的小整数（$1\le M\le 100$）。
下一行是 $1$ 到 $N$ 这 $N$ 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

== 输出格式==

$N$ 个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

输入

5
3
1 2 3 4 5

== 输出 #1==

1 2 4 5 3

说明/提示

对于 $30\%$ 的数据，$N\le 15$。

对于 $60\%$ 的数据，$N\le 50$。

对于 $100\%$ 的数据，$N\le 10000$。

noip2004 普及组第 4 题

解题思路：这道题如果用dfs来做的话，会稍有复杂，但是没关系，我们今天学习了全排列函数，那可太棒了，简直易如反掌！别看题目这么长，这道题就是让我们从他给出的这个数组原始顺序开始，改变后的排雷顺序，我们只需让他进行m次全排列就可以了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10005;
int n,m,a[N];
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)next_permutation(a+1,a+1+n);for(int i=1;i<=n;i++)cout<<a[i]<<" ";return 0;
}

大致内容就这些_{动动您发财的小手，点个赞吧}