The Next Permutation Algorithm in C++ (std::next_permutation)

  • 时间:2020-09-18 17:39:21
  • 分类:网络文摘
  • 阅读:87 次

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().

6494F03B-2089-487C-90BD-44BDD78ACBB1-300x146 The Next Permutation Algorithm in C++ (std::next_permutation) algorithms c / c++

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) —

推荐阅读:
5 Tips for Staying Safe Online  10 Signs Your Blog is Working  The Key to Risk-Free Cloud-Based IT Equipment Shipping  Bring Your Multi-Site Development Work To The Next Level With A   
How to Create Killer SEO Content on a Budget  Learn to Achieve Your Goals with 5 Secrets of Great Bloggers  What is Cornerstone Content And Why It’s Important  How to Attract Female Readership For Your Blog  Double your traffic with White Hat SEO techniques  Blogging As Therapy: True Life Stories Of Victims And How They C 
评论列表
添加评论