The Next Permutation Algorithm in C++ (std::next_permutation)
- 时间:2020-09-18 17:39:21
- 分类:网络文摘
- 阅读:91 次
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
std::permutation in C++
The C++ std::permutation() takes two parameters, the start iterator and the finishing iterator (one element beyond), then returns its next permutation.
Therefore, by using the std::permutation(), we can easily solve the problem – without re-inventing the wheel.
1 2 3 4 5 6 7 | class Solution { public: void nextPermutation(vector<int>& nums) { if (nums.empty()) return; next_permutation(begin(nums), end(nums)); } }; |
class Solution { public: void nextPermutation(vector<int>& nums) { if (nums.empty()) return; next_permutation(begin(nums), end(nums)); } };
If not such permutation is possible e.g. the last permutation, then the next_permutation() will return false and set the permutation to the first permutation the smallest in the ascending order. For example, 54321’s next permutation will be 12345.
Implement the Next Permutation Algorithm
During an interview, the interviewer will not be looking for the above solution. Rather he/she will need the interviewee to implement the next_permutation().

Next Permutation Algorithm
As shown in the above animation, we need to scan backwards and find the first decreasing element. Then, we need to swap it with the next largest number. At least, the sub-vectors need to be reversed using std::reverse().
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public: void nextPermutation(vector<int>& nums) { int sz = nums.size(); if (sz <= 1) return; int i = sz - 2; // find the decreasing element while ((i >= 0) && (nums[i] >= nums[i + 1])) --i; if (i >= 0) { // if there is.. int j = sz - 1; // find next larger number while ((j >= i) && (nums[j] <= nums[i])) { -- j; } swap(nums[i], nums[j]); } std::reverse(begin(nums) + i + 1, end(nums)); } }; |
class Solution { public: void nextPermutation(vector<int>& nums) { int sz = nums.size(); if (sz <= 1) return; int i = sz - 2; // find the decreasing element while ((i >= 0) && (nums[i] >= nums[i + 1])) --i; if (i >= 0) { // if there is.. int j = sz - 1; // find next larger number while ((j >= i) && (nums[j] <= nums[i])) { -- j; } swap(nums[i], nums[j]); } std::reverse(begin(nums) + i + 1, end(nums)); } };
The complexity is O(N) and a constant space is required. This puzzle is known to be asked during a onsite facebook coding interview.
Don’t forget to give your algorithmic complexity which is O(N).
Refer to C++ std::next_permutation() for more advanced tutorial.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:立顿茶系列饮品被指农药超标 雅培配方奶粉被曝不符合安全标准 营养和安全:有机食品PK常规食品 蔬菜如何烹制,营养、健康又安全 八种简易食疗方,巧防春季流感 春季养生:喝花茶可护肝,预防感冒 农夫山泉被质疑标准不及自来水 北京工商局4月10日食品安全信息 保健养生:果蔬是“抗癌”食品首选 国家食药总局曝光10种假冒保健食品
- 评论列表
-
- 添加评论