Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::next_permutation — next lexicographical permutation

std::next_permutation rearranges a range into its next lexicographical permutation. It returns true when a successor exists; after the final permutation, it restores the first arrangement and returns false.

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

Syntax

#include <algorithm>

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

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

std::next_permutation from <algorithm> modifies the range [first, last) in place. Lexicographical order is determined by the first position where the elements of two arrangements are not equivalent under the chosen comparison. The overload without comp uses the default less-than comparison; the overload with comp uses that comparator to define the order.

A result of true means that a successor was found. A result of false does not mean that the data was left unchanged: the algorithm restores the first arrangement, sorted in ascending order under the chosen comparison. An empty or single-element range returns false.

The iterators must be bidirectional, and their referenced elements must support swapping values. comp must define a strict weak ordering; do not use <=. For N elements, the standard limits the number of swaps to N / 2.

Start with a range sorted under the same comparison and use do–while so the initial arrangement is processed too. The loop visits one arrangement for each distinct sequence of equivalence classes defined by the comparison. If the comparison treats unequal values as equivalent, the loop can skip some distinct value sequences. In the example, the default comparison distinguishes 1 from 2, so the loop prints all three distinct value arrangements. The example also shows the state after the final call returns false.

Examples

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

int main() {
    std::array<int, 3> values{1, 1, 2};
    do {
        std::cout << values[0] << ' ' << values[1] << ' '
                  << values[2] << '\n';
    } while (std::next_permutation(values.begin(), values.end()));

    std::cout << "reset: " << values[0] << ' ' << values[1]
              << ' ' << values[2] << '\n';
}

Result

1 1 2
1 2 1
2 1 1
reset: 1 1 2

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