The Elegant Internal Implementation of C++ std::next_permutation

The C++ Standard Library is full of powerful, efficient functions. One that often feels like magic is std::next_permutation. It takes a sequence of elements and, in a flash, rearranges it into the very next lexicographically greater order.

It's incredibly fast, even for large collections, which begs the question: how does it work? How does it avoid the massive computational cost you might expect from a permutation problem?

I decided to dig in, and it turns out the algorithm is a fantastic lesson in clever, efficient design. It doesn't need to generate every possibility; instead, it makes the smallest possible change to find the next sequence.

The Algorithm: A Step-by-Step Walkthrough

The standard library algorithm is clever because it realizes you just need to figure out how to make the smallest possible change to the current sequence to make it lexicographically larger.

The logic is similar to how you'd manually find the next largest number using the same set of digits. For example, to get from 18765 to the next largest number, you wouldn't start changing the 1. You'd start from the right and work your way left.

Let's walk through the exact same logic with the sequence [1, 8, 7, 6, 5].

1. Find the Pivot. We scan from right to left to find the first element that is smaller than its right-hand neighbor. This element is our "pivot"—the key to making the sequence larger.

   • 5 has no right neighbor.
   • 6 is larger than 5.
   • 7 is larger than 6.
   • 8 is larger than 7.
   • 1 is smaller than 8. We found our pivot. It's 1.
   • The sequence is [1, | 8, 7, 6, 5]. The section to the right of the pivot is the "suffix." Notice it's sorted in descending order, meaning it's already at its maximum possible arrangement.

2. Find the Pivot's Successor. Now, we look only within the suffix ([8, 7, 6, 5]). We need to find the smallest element that is still larger than our pivot (1).

   • That element is 5.

3. Swap them. Swap the pivot (1) with its successor (5).

   • The sequence is now: [5, | 8, 7, 6, 1]

4. Sort the Suffix. We've successfully made the prefix of the sequence larger. To ensure it's the very next permutation, we must make the suffix as small as possible. Since the suffix [8, 7, 6, 1] was in descending order before the swap, the most efficient way to sort it ascending is to simply reverse it.

   • Reverse [8, 7, 6, 1] to get [1, 6, 7, 8].

5. The Result. The final sequence is [5, 1, 6, 7, 8]. We found it in a single pass, without generating any other permutations.

The Algorithm in C++

This logic maps beautifully onto C++ STL components. Using reverse iterators makes the right-to-left scan clean and simple.

#include <vector>
#include <algorithm>
#include <iterator>
 
bool next_permutation(
    std::vector<int>::iterator first, 
    std::vector<int>::iterator last
) {
    // Use reverse iterators to scan from right to left
    auto r_first = std::make_reverse_iterator(last);
    auto r_last = std::make_reverse_iterator(first);
 
    // 1. Find the pivot. `is_sorted_until` on a reversed range does this perfectly.
    auto pivot = std::is_sorted_until(r_first, r_last);
 
    // If the entire sequence is sorted in descending order, we're at the last permutation.
    if (pivot == r_last) {
        std::reverse(first, last); // Reset to the first permutation (fully sorted)
        return false;
    }
 
    // 2. Find the successor. `upper_bound` is the right tool for finding the first
    //    element greater than the pivot in the sorted (descending) suffix.
    auto successor = std::upper_bound(r_first, pivot, *pivot);
 
    // 3. Swap the pivot and its successor.
    std::iter_swap(pivot, successor);
 
    // 4. Reverse the suffix. `pivot.base()` converts the reverse_iterator
    //    back to a forward_iterator pointing to the start of the suffix.
    std::reverse(pivot.base(), last);
 
    return true;
}

This approach is not only cleaner but drastically more efficient. Because it operates in-place and typically only modifies the end of the sequence, its average time complexity is amortized O(1), with a worst-case of O(N) only when the entire sequence must be reversed. Its space complexity is O(1).

Final Thoughts

Looking under the hood of a standard library function like std::next_permutation is more than just an academic exercise. It reveals the clever thinking that makes the STL so powerful. The algorithm's single-pass, in-place approach is a perfect example of how a deep insight into a problem can lead to a solution that is both elegant and highly efficient. It’s a great reminder of the power and thoughtful design baked into the tools we use every day.