Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::prev_permutation — prethodna leksikografska permutacija

std::prev_permutation preslaže raspon u njegovu prethodnu leksikografsku permutaciju. Vraća bool; ako prethodna permutacija ne postoji, postavlja posljednju permutaciju i vraća false.

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

Sintaksa

#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, deklariran u <algorithm>, mijenja [first, last) na mjestu i stvara neposredno prethodni raspored u leksikografskom poretku. Poredak određuje prvo mjesto na kojem vrijednosti nisu ekvivalentne prema komparatoru. U C++23 za zadanu se usporedbu upotrebljava std::less{}, koji jamči strog potpuni poredak pokazivača i ondje gdje ga ugrađeni operator < ne jamči. Preopterećenje koje prima comp omogućuje zadavanje drugog strogog slabog poretka.

Povratna vrijednost true znači da je pronađena prethodna permutacija. Vrijednost false ne znači da su podaci ostali nepromijenjeni: algoritam stvara posljednju permutaciju, odnosno silazni poredak prema odabranom poretku. Za prazan raspon ili raspon s jednim elementom vraća false, a sadržaj ostaje isti.

Algoritam zahtijeva dvosmjerne iteratore čije se referencirane vrijednosti mogu zamijeniti. Podatke ne treba prethodno sortirati za jedan korak. Ako komparator razlikuje svaki par različitih vrijednosti u rasponu, počnite od silaznog rasporeda i upotrijebite petlju do–while kako biste prošli kroz svaki različiti raspored vrijednosti točno jednom, od najvećeg prema najmanjem. Ako komparator različite vrijednosti smatra ekvivalentnima, algoritam razlikuje samo rasporede njihovih klasa ekvivalencije pa može preskočiti neke rasporede vrijednosti. Na primjer, ako raspon sadrži samo dvije različite vrijednosti koje su prema komparatoru ekvivalentne, već prvi poziv vraća false.

Primjer prikazuje prijelaze između permutacija i povratak na posljednju permutaciju nakon rezultata false. Ovaj zapis opisuje preopterećenja std::prev_permutation koja vraćaju bool, a ne sučelje std::ranges.

Primjeri

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

Rezultat

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

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori