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

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.

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

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.

C/C++ Programming

• Understanding std::transform_reduce in Modern C++
• Implement a Lock Acquire and Release in C++
• Detecting Compile-time vs Runtime in C++: if consteval vs std::is_constant_evaluated()
• C++ Forward References: The Key to Perfect Forwarding
• Understanding dynamic_cast in C++: Safe Downcasting Explained
• C vs C++: Understanding the restrict Keyword and its Role in Optimization
• C++ Lvalue, Rvalue and Rvalue References
• C++ assert vs static_assert
• Why auto_ptr is Deprecated in C++?
• C++ What is the consteval? How is it different to const and constexpr?
• Tutorial on C++ std::move (Transfer Ownership)
• const vs constexpr in C++
• Tutorial on C++ Ranges
• Tutorial on C++ Smart Pointers
• Tutorial on C++ Future, Async and Promise
• The Memory Manager in C/C++: Heap vs Stack
• The String Memory Comparision Function memcmp() in C/C++
• Modern C++ Language Features
• Comparisions of push_back() and emplace_back() in C++ std::vector
• C++ Coding Reference: is_sorted_until() and is_sorted()
• C++ Coding Reference: iota() Setting Incrementing Values to Arrays or Vectors
• C++ Coding Reference: next_permutation() and prev_permutation()
• C++ Coding Reference: count() and count_if()
• C++ Code Reference: std::accumulate() and Examples
• C++ Coding Reference: sort() and stable_sort()
• The Next Permutation Algorithm in C++ std::next_permutation()

–EOF (The Ultimate Computing & Technology Blog) —