C++ Coding Reference: next_permutation() and prev_permutation()
- 时间:2020-09-17 14:37:27
- 分类:网络文摘
- 阅读:89 次
C++ algorithm header provides you access to next_permutation() and prev_permutation() which can be used to obtain the next or previous lexicographically order. With an array or vector or string (or other STL containers) of size N, there are total N! (factorial) permutations. The (next or previous) permutation algorithms are mostly in-place which mean that it will modify the given list or vector.
The C++ permutation algorithm functions are quite handy, which can be used to solve algorithm puzzles, like the following:
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
1 2 3 4 5 6 7 8 [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ][ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
std::next_permutation()
The std::next_permutation() takes 3 parameters, the first two are mandatory/required while the third one is the optional. The first parameter is the start of the container (which could be vector/array or string), and the second parameter marks the end of the STL container. For example:
1 2 | vector<int> nums({1, 2, 3, 4, 5}); next_permutation(begin(nums), end(nums)); // nums is now {1, 2, 3, 5, 4} |
vector<int> nums({1, 2, 3, 4, 5}); next_permutation(begin(nums), end(nums)); // nums is now {1, 2, 3, 5, 4}
The third parameter is used to provide a custom lexicographical comparator. The above example is essentially the same as the following:
1 2 3 4 | vector<int> nums({1, 2, 3, 4, 5}); next_permutation(begin(nums), end(nums), [](auto &a, auto &b) { return a < b; }); // nums is now {1, 2, 3, 5, 4} |
vector<int> nums({1, 2, 3, 4, 5}); next_permutation(begin(nums), end(nums), [](auto &a, auto &b) { return a < b; }); // nums is now {1, 2, 3, 5, 4}
The std::next_permutation() will permutate the vector container and return if there is still a next permutation. For example:
1 2 3 4 5 6 | vector<int> nums({1, 2, 3, 4, 5}); // nums is now {1, 2, 3, 5, 4} and the function returns true next_permutation(begin(nums), end(nums)); vector<int> nums2({5, 4, 3, 2, 1}); // nums2 is now {1, 2, 3, 4, 5} and the function returns false next_permutation(begin(nums2), end(nums2)); |
vector<int> nums({1, 2, 3, 4, 5}); // nums is now {1, 2, 3, 5, 4} and the function returns true next_permutation(begin(nums), end(nums)); vector<int> nums2({5, 4, 3, 2, 1}); // nums2 is now {1, 2, 3, 4, 5} and the function returns false next_permutation(begin(nums2), end(nums2));
It is worth to note that, when the original list is considered the last lexicographical order, the next_permutation() will still permutate the list which virtually rewinds to first lexicographical sequence.
Now, we can easily solve the algorithm puzzle mentioned at the beginning – don’t forget to push the current order into the final list.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: vector<vector<in>> permute(vector<int>& nums) { vector<vector<int>> r; sort(begin(nums), end(nums)); r.push_back(nums); while (next_permutation(begin(nums), end(nums))) { r.push_back(nums); } return r; } }; |
class Solution { public: vector<vector<in>> permute(vector<int>& nums) { vector<vector<int>> r; sort(begin(nums), end(nums)); r.push_back(nums); while (next_permutation(begin(nums), end(nums))) { r.push_back(nums); } return r; } };
We need to sort the original vector so that all permutations can be returned. The algorithm complexity is dominated by sorting which is O(NlogN). The next_permutation() runs at O(N) complexity.
std::prev_permutation()
Syntactically, the std::prev_permutation() is the same as next_permutation() however it returns the last lexicographical sequence/order. We can easily deduce that, the next_permutation() is the same as prev_permutation() when passing the third parameter as the reversed version. For example, the following two are equivalently the same.
1 2 3 4 5 6 | next_permutation(begin(nums), end(nums), [](auto &a, auto &b) { return a < b; }); prev_permutation(begin(nums), end(nums), [](auto &a, auto &b) { return a > b; }); |
next_permutation(begin(nums), end(nums), [](auto &a, auto &b) { return a < b; }); prev_permutation(begin(nums), end(nums), [](auto &a, auto &b) { return a > b; });
We can also use next_permutation() or prev_permutation() on strings. For example:
1 2 3 | string s = "12345"; next_permutation(begin(s), end(s)); // s becomes 12354 prev_permutation(begin(s), end(s)); // s becomes 12345 |
string s = "12345"; next_permutation(begin(s), end(s)); // s becomes 12354 prev_permutation(begin(s), end(s)); // s becomes 12345
We can also use prev_permutation() to solve the puzzle:
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: vector<vector<in>> permute(vector<int>& nums) { vector<vector<int>> r; sort(rbegin(nums), rend(nums)); // sorting in the reverse order r.push_back(nums); while (prev_permutation(begin(nums), end(nums))) { r.push_back(nums); } return r; } }; |
class Solution { public: vector<vector<in>> permute(vector<int>& nums) { vector<vector<int>> r; sort(rbegin(nums), rend(nums)); // sorting in the reverse order r.push_back(nums); while (prev_permutation(begin(nums), end(nums))) { r.push_back(nums); } return r; } };
One difference is to sort the original array in the reverse order – by passing the reverse iterators e.g. rbegin() and rend(). Alternatively, we can use std::reverse() after the usual sort() in ascending order.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:创业项目营销效果不佳 只因没做好这几件事 AI把英语系新生吓退学?别急,我们从来都是那只懒蚂蚁 创业初期该做什么?首先你需要避开的这5大坑! 2018世界人工智能大会开幕,它给创业者带来了哪些思路? 创业寒冬下 初创公司如何才可以打破C轮死魔咒? 为什么企业找不到合适的互联网营销负责人? 知识焦虑遇冷后 知识付费的下一个风口究竟在哪里? 2018秋北京松松兄弟线下聚会干货分享 赌徒谬误:究竟谁在交易所玩合约? 免费的午餐
- 评论列表
-
- 添加评论