文章目录
前言一、next_permutation()用法简单使用例子1第m个最小的数字序列 自定义排序大小写字母排序 二、prev_permutation()用法三、STL next_permutation和prev_permutation 算法原理参考前言
字节三面，考了leetcode556题，复盘发现了两个超好用的函数，C++STL中的全排列函数为两个：next_permutation和prev_permutation
其中：next_permutation实现升序，而prev_permutation实现降序。
一、next_permutation()用法
next_permutation()函数的返回类型是bool类型。
即：如果有一个更高的排列，它重新排列元素，并返回true；如果这是不可能的（因为它已经在最大可能的排列），它按升序排列重新元素，并返回false。
使用：
next_permutation，重新排列范围内的元素[第一，最后一个）返回按照字典序排列的下一个值较大的组合。
next_permutation()函数功能是输出所有比当前排列大的排列，顺序是从小到大。
算法描述：
1、从尾部开始往前寻找两个相邻的元素
第1个元素i，第2个元素j（从前往后数的），且i<j
2、再从尾往前找第一个大于i的元素k。将i、k对调
3、[j,last)范围的元素置逆（颠倒排列）
简单使用
例子1
#include <iostream>#include <algorithm>using namespace std;int main() {char data1[] = "abcd";char data2[] = "bcad";char data3[] = "abcc";char data4[] = "1234";char data5[] = "3124";char data6[] = "1233";do {puts(data1);} while (next_permutation(data1, data1 + 4));cout << endl;do {puts(data2);} while (next_permutation(data2, data2 + 4));cout << endl;do {puts(data3);} while (next_permutation(data3, data3 + 4));cout << endl;do {puts(data4);} while (next_permutation(data4, data4 + 4));cout << endl;do {puts(data5);} while (next_permutation(data5, data5 + 4));cout << endl;do {puts(data6);} while (next_permutation(data6, data6 + 4));cout << endl;system("pause");return 0;}
结果：
abcdabdcacbdacdbadbcadcbbacdbadcbcadbcdabdacbdcacabdcadbcbadcbdacdabcdbadabcdacbdbacdbcadcabdcbabcadbcdabdacbdcacabdcadbcbadcbdacdabcdbadabcdacbdbacdbcadcabdcbaabccacbcaccbbaccbcacbccacabccacbcbaccbcaccabccba123412431324134214231432213421432314234124132431312431423214324134123421412341324213423143124321312431423214324134123421412341324213423143124321123313231332213323132331312331323213323133123321
第m个最小的数字序列
题目：给定一个从1到N的序列，我们定义1,2,3…N-1,N，是所有可以由1到N组成的序列中最小的序列（每个数字只能使用一次）。 因此，很容易看到第二个最小的序列是1,2,3…N，N-1。 现在我给你两个数字N和M。你应该告诉我第M个最小的序列，它由1到N组成。输入：每个测试用例均包含两个数字N和M（1 <= N <= 1000，1 <= M <= 10000）。 您可能会假设总是有一个序列满足BEelzebub的需求。 输入在文件末尾终止。6 4
11 8输出：对于每个测试用例，您只需输出满足BEelzebub要求的序列即可。 输出序列时，应在两个数字之间打印一个空格，但不要在最后一个数字之后输出任何空格。
1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10
#include<cstdio> #include<algorithm>#include<vector>#include <iostream>using namespace std;int main(){int n, m;while (cin>>n>>m){vector<int> a(n,0);for (int i = 0; i < n; i++)a[i] = i + 1;int num = 0;do{num++;if (num == m){for (int i = 0; i < n; i++){if (i == 0){cout << a[i];}elsecout << " " << a[i];}cout << endl;break;}} while (next_permutation(a.begin(), a.end()));}system("pause");return 0;}
自定义排序
大小写字母排序
题目：您将要编写一个程序，该程序必须根据给定的字母集生成所有可能的单词。示例：给定单词“ abc”，您的程序应-通过探索三个字母的所有不同组合-输出单词“ abc”，“ acb”，“ bac”，“ bca”，“ cab”和“ cba”。
在从输入文件中提取的单词中，某些字母可能会出现多次。 对于给定的单词，您的程序不应多次产生相同的单词，并且单词应按字母升序输出。输入：输入由几个词组成。 第一行包含一个数字，给出要跟随的单词数。 接下来的每一行包含一个单词。 单词由A到Z的大写或小写字母组成。大写和小写字母应被视为不同。 每个单词的长度小于13。
Sample Input：
3
aAb
abc
acba输出：对于输入中的每个单词，输出应包含可以使用给定单词的字母生成的所有不同单词。 由相同输入单词生成的单词应按字母升序输出。 大写字母位于相应的小写字母之前。
Sample Output
Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa
#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>using namespace std;int cmp(char a, char b) //自定义函数,实现字母大写排在小写前面的功能{if (tolower(a) != tolower(b)) //tolower是将大写转化为小写,A-Z 65-90 a-z 97-122return tolower(a) < tolower(b);elsereturn a < b;}int main(){int n;cin >> n;string s="";while (n--){cin >> s;int len = s.size();sort(s.begin(), s.end(), cmp);do{cout << s << endl;} while (next_permutation(s.begin(), s.end(), cmp)); //自定义函数的使用}system("pause");return 0;}
二、prev_permutation()用法
prev_permutation()函数功能是输出所有比当前排列小的排列，顺序是从大到小。
例子：
#include <iostream>#include <algorithm>using namespace std;int main() {char data1[] = "dbca";char data2[] = "bcad";char data3[] = "dbcc";char data4[] = "4321";char data5[] = "3124";char data6[] = "3312";do {puts(data1);} while (prev_permutation(data1, data1 + 4));cout << endl;do {puts(data2);} while (prev_permutation(data2, data2 + 4));cout << endl;do {puts(data3);} while (prev_permutation(data3, data3 + 4));cout << endl;do {puts(data4);} while (prev_permutation(data4, data4 + 4));cout << endl;do {puts(data5);} while (prev_permutation(data5, data5 + 4));cout << endl;do {puts(data6);} while (prev_permutation(data6, data6 + 4));cout << endl;system("pause");return 0;}
结果：
dbcadbacdacbdabccdbacdabcbdacbadcadbcabdbdcabdacbcdabcadbadcbacdadcbadbcacdbacbdabdcabcdbcadbadcbacdadcbadbcacdbacbdabdcabcddbcccdcbcdbcccdbccbdcbdccbcdbdccbcdcbccd432143124231421341324123342134123241321431423124243124132341231421432134143214231342132412431234312424312413234123142143213414321423134213241243123433123231321331323123233123132133133213231233
三、STL next_permutation和prev_permutation 算法原理
算法原理
参考
参考文章1
参考文章2
我不会，我可以学！
