C++ Coding Reference: next_permutation() and prev_permutation()

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],
  [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:

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:

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:

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.

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.

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:

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:

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.

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