Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::prev_permutation — previous lexicographical permutation

std::prev_permutation rearranges a range into its previous lexicographical permutation. It returns bool; when no previous permutation exists, it rearranges the range into the last permutation and returns false.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>

template<class BidirectionalIterator>
constexpr bool prev_permutation(BidirectionalIterator first,
                                BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
constexpr bool prev_permutation(BidirectionalIterator first,
                                BidirectionalIterator last,
                                Compare comp);

std::prev_permutation, declared in <algorithm>, modifies [first, last) in place to produce the immediately preceding arrangement in lexicographical order. The order is determined by the first position where the values are not equivalent under the comparator. In C++23, the default comparator is std::less{}, which guarantees a strict total order for pointers even where built-in < does not. The overload taking comp lets you supply another strict weak ordering.

A return value of true means a previous permutation was found. A return value of false does not mean the data was left unchanged: the algorithm produces the last permutation, descending under the chosen ordering. For an empty or single-element range, it returns false and the contents remain the same.

The algorithm requires bidirectional iterators whose referenced values can be swapped. You do not need to sort the data before taking one step. If the comparator distinguishes every pair of distinct values in the range, start in descending order and use a do–while loop to visit each distinct value arrangement exactly once, from greatest to least. If distinct values compare equivalent, the algorithm distinguishes only arrangements of their equivalence classes, so some value arrangements may be skipped. For example, if the range contains only two distinct values that compare equivalent, the first call already returns false.

The example demonstrates both transitions between permutations and the wrap to the last permutation after false. This entry describes the std::prev_permutation overloads returning bool, not the std::ranges interface.

Examples

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    std::array<int, 3> values{2, 1, 1};
    std::cout << std::boolalpha;

    bool found;
    do {
        for (int value : values) {
            std::cout << value;
        }
        found = std::prev_permutation(values.begin(), values.end());
        std::cout << " -> " << found << '\n';
    } while (found);

    std::cout << "after wrap: ";
    for (int value : values) {
        std::cout << value;
    }
    std::cout << '\n';
}

Result

211 -> true
121 -> true
112 -> false
after wrap: 211

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources