Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

std::next_permutation — naslednja leksikografska permutacija

std::next_permutation preuredi obseg v njegovo naslednjo leksikografsko permutacijo. Vrne true, če naslednja permutacija obstaja; po zadnji obnovi prvo razporeditev in vrne false.

Različica: C++23; repository compiler flag, production runtime not attested

Sintaksa

#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 iz <algorithm> neposredno spremeni obseg [first, last). Leksikografski vrstni red dveh razporeditev določa prvo mesto, na katerem njuna elementa glede na uporabljeno primerjavo nista ekvivalentna. Preobremenitev brez comp uporablja privzeto primerjavo »manj kot«; preobremenitev s comp določi vrstni red s tem primerjalnikom.

Rezultat true pomeni, da je bila najdena naslednja razporeditev. Rezultat false ne pomeni, da so podatki ostali nespremenjeni: algoritem obnovi prvo razporeditev, urejeno naraščajoče glede na uporabljeno primerjavo. Za prazen obseg ali obseg z enim elementom vrne false.

Iteratorji morajo biti dvosmerni, elementi, na katere kažejo, pa morajo omogočati zamenjavo vrednosti. comp mora določati strogo šibko urejenost; ne uporabljajte <=. Za N elementov standard omejuje število zamenjav na N / 2.

Začnite z obsegom, urejenim po isti primerjavi, in uporabite do–while, da obdelate tudi začetno razporeditev. Zanka obišče po eno razporeditev za vsako različno zaporedje ekvivalenčnih razredov, ki jih določa primerjava. Če primerjava obravnava različne vrednosti kot ekvivalentne, lahko zanka nekatera različna zaporedja vrednosti preskoči. V primeru privzeta primerjava razlikuje med 1 in 2, zato zanka izpiše vse tri različne razporeditve vrednosti. Primer prikazuje tudi stanje po zadnjem klicu, ki vrne false.

Primeri

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

Rezultat

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

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri