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