0%

STL——next_permutation&prev_permutation

next_permutation和prev_permutation是对c++求全排列的函数,分别可以求出下一个全排列和前一个全排列。

这里以next_permutation为例,来看一下c++官网的定义:

default: bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);
custom: bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

可以看到和sort的用法很像,只需要输入first和last就可以返回是否有下一个,如果有的话会直接在内部排序出现下一个。

同时可以选项是comp函数,可以自定义排序方式,默认为字典序。

例子

题目:leetcode 46. Permutations

这是一道全排列的题目,普通解法有dfs和非递归的查找,看解答时发现了这个函数,减少了不少代码量。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
if (nums.size() == 0) return ans;
sort(nums.begin(), nums.end());
ans.push_back(nums);
while (next_permutation(nums.begin(), nums.end())) {
ans.push_back(nums);
}
return ans;
}
};

搬运自CSDN:https://blog.csdn.net/yueyue200830/article/details/86771956