Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::prev_permutation — predchádzajúca lexikografická permutácia

std::prev_permutation preusporiada rozsah na jeho predchádzajúcu lexikografickú permutáciu. Vráti bool; ak predchádzajúca permutácia neexistuje, nastaví poslednú permutáciu a vráti false.

Verzia: 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 deklarovaná v <algorithm> mení [first, last) priamo a vytvorí bezprostredne predchádzajúce usporiadanie v lexikografickom poradí. O poradí rozhoduje prvá pozícia, na ktorej hodnoty podľa komparátora nie sú ekvivalentné. V C++23 sa na predvolené porovnávanie používa std::less{}, ktoré zaručuje striktné úplné usporiadanie ukazovateľov aj tam, kde ho vstavaný operátor < nezaručuje. Preťaženie prijímajúce comp umožňuje zadať iné striktne slabé usporiadanie.

Návratová hodnota true znamená, že sa našla predchádzajúca permutácia. Hodnota false neznamená, že údaje zostali nezmenené: algoritmus vytvorí poslednú permutáciu, teda zostupné usporiadanie podľa zvoleného usporiadania. Pre prázdny rozsah alebo rozsah s jediným prvkom vráti false a obsah zostane rovnaký.

Algoritmus vyžaduje obojsmerné iterátory, ktorých odkazované hodnoty možno zamieňať. Pred vykonaním jedného kroku netreba údaje triediť. Ak komparátor rozlišuje každú dvojicu rôznych hodnôt v rozsahu, začnite zostupným usporiadaním a použite cyklus do–while. Tak prejdete každé odlišné usporiadanie hodnôt práve raz, od najväčšieho po najmenšie. Ak komparátor považuje rôzne hodnoty za ekvivalentné, algoritmus rozlišuje len usporiadania ich tried ekvivalencie, takže niektoré usporiadania hodnôt môže preskočiť. Ak napríklad rozsah obsahuje len dve rôzne hodnoty, ktoré sú podľa komparátora ekvivalentné, už prvé volanie vráti false.

Príklad ukazuje prechody medzi permutáciami aj návrat k poslednej permutácii po výsledku false. Tento záznam opisuje preťaženia std::prev_permutation, ktoré vracajú bool, nie rozhranie std::ranges.

Príklady

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

Výsledok

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

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje