排列是暴力枚举时的常见操作。有以下两种情况。
C++的 next_permutation()是全排列函数,只能输出序列中所有元素的全排列。
本节将给出手写排列和组合的代码。因为在很多场合中不能使用系统自带的排列函数,所以需要自己编写。
全排列函数:next_permutation()
STL提供了求下一个排列组合的函数next_permutation()。例如对于由3个字符{a,b, c}组成的序列,next_permutation()能按字典序返回6个组合:abc、acb、bac、bca、cab、cba。
函数next_permutation()的定义有以下两种形式:
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);
返回值:如果没有下一个排列组合,则返回False,否则返回True。每执行一次next_ permutation(),新的排列就会被放到原来的空间里。
简称:前闭后开。
next_permutation()从当前的全排列开始,逐个输出更大的全排列,而不是输出所有的全排列,例如下面的代码。
#include <bits/stdc++.h>
using namespace std;
int main() {string s=”bca”;do {cout<<s<< " ";} while(next_permutation(s.begin(),s.end()));return 0;
} //输出:bca cab cba
如果要得到所有的全排列,就需要从最小的全排列开始。如果初始的全排列不是最小的,则需要先用sort()对全排列排序,得到最小的全排列后,再使用next_permutation(),例如下面的代码。
#include <bits/stdc++.h>
using namespace std;
int main() {string s=”bca”;sort(s.begin(),s.end()); //字符串内部排序,得到最小的排列“abc”do {cout<<s<< " ";} while(next_permutation(s.begin(),s.end()));return 0;
} //输出:abc acb bac bca cab cba
C++中还有一个全排列函数prev_permutation(),用于求前一个排列组合,与next_permutation()相反,即从大到小输出排列。
手写排列代码(暴力法):
#include <iostream>
#include <vector>//排列
int main() {std::vector<int> s = {1, 2, 3, 4};for (int i = 0; i < 4; ++i) {for (int j = 0; j < 4; ++j) {if (j != i) {for (int k = 0; k < 4; ++k) {if (k != j && k != i) {std::cout << s[i] << s[j] << s[k] << ", ";}}}}}return 0;
}
手写组合代码(暴力法):
#include <iostream>
#include <vector>int main() {std::vector<int> s = {1, 2, 3, 4};for (int i = 0; i < 4; ++i) {for (int j = i + 1; j < 4; ++j) {for (int k = j + 1; k < 4; ++k) {std::cout << s[i] << s[j] << s[k] << ", ";}}}return 0;
}
例题1.排列序数
思路:先对输入的字符串s排序,然后用next_permutation()输出全排列,当全排列与初始的字符串相等时结束。
代码:
#include <bits/stdc++.h>
using namespace std;
int main() {string s,olds;cin>>s;olds=s; //用olds记录最初的字符串int cnt = 0;sort(s.begin(),s.end()); //字符串内部排序,得到最小的排列do {if(s == olds) {cout<<cnt<<endl;break;}cnt++;} while(next_permutation(s.begin(),s.end()));return 0;
}
例题2.拼数
代码:
#include<bits/stdc++.h>
using namespace std;
string a[21]; //记录20个数,用字符形式
bool cmp (string a, string b) { //从大到小,按字典序的反序排列return a + b > b + a; //组合字符串,注意这个技巧,后面会详细讲解
}
int main( ) {int n;cin >> n;for(int i=0; i<n; i++) cin >> a[i];sort(a, a+n, cmp); //从大到小,按字典序的反序排列for(int i=0; i<n; i++) cout << a[i];return 0;
}
函数体中的这行代码:
return a + b > b + a;
是一个巧妙的比较方式,用于实现按字典序的反序(即从大到小)排列字符串。
如果 a + b 大于 b + a,说明 a 在字典序上大于 b,因此返回 true。
如果 a + b 小于 b + a,说明 a 在字典序上小于 b,因此返回 false。
如果它们相等,说明 a 和 b 相等,但由于我们在排序时通常不需要处理相等的情况,所以这个比较方式在这种情况下也能正常工作。