Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::prev_permutation — poprzednia permutacja leksykograficzna

std::prev_permutation przestawia elementy zakresu na poprzednią permutację w porządku leksykograficznym. Zwraca bool; gdy poprzednia permutacja nie istnieje, ustawia ostatnią permutację i zwraca false.

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

Składnia

#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 z nagłówka <algorithm> modyfikuje zakres [first, last) w miejscu, wybierając bezpośrednio poprzednie ułożenie w porządku leksykograficznym. O kolejności decyduje pierwsza pozycja, na której porównywane wartości nie są równoważne według komparatora. W C++23 do porównywania domyślnie używa się std::less{}, które zapewnia ścisły porządek całkowity dla wskaźników także tam, gdzie wbudowany operator < go nie gwarantuje. Przeciążenie z comp pozwala określić inny ścisły słaby porządek.

Wynik true oznacza znalezienie poprzedniej permutacji. Wynik false nie oznacza pozostawienia danych bez zmian: algorytm ustawia ostatnią permutację, czyli malejącą według przyjętego porządku. Dla zakresu pustego lub jednoelementowego zwraca false, a zawartość pozostaje taka sama.

Wymagane są iteratory dwukierunkowe oraz możliwość zamiany wskazywanych wartości. Nie trzeba wcześniej sortować danych, aby wykonać jeden krok. Jeśli komparator rozróżnia każdą parę różnych wartości w zakresie, zacznij od porządku malejącego i użyj pętli do–while, aby odwiedzić każde różne ułożenie wartości dokładnie raz, od największego do najmniejszego. Jeśli komparator uznaje różne wartości za równoważne, algorytm rozróżnia tylko ułożenia ich klas równoważności, więc może pominąć niektóre ułożenia wartości. Na przykład w zakresie zawierającym tylko dwie różne wartości równoważne według komparatora już pierwsze wywołanie zwraca false.

Przykład pokazuje zarówno przejścia między permutacjami, jak i powrót do ostatniej po wyniku false. Opis dotyczy przeciążeń std::prev_permutation, które zwracają bool, a nie interfejsu std::ranges.

Przykłady

#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';
}

Wynik

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

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła