Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::next_permutation — sljedeća leksikografska permutacija

std::next_permutation preuređuje raspon u njegovu sljedeću leksikografsku permutaciju. Vraća true ako postoji sljedeća permutacija; nakon posljednje obnavlja prvi raspored i vraća false.

Verzija: 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> mijenja raspon [first, last) na mjestu. Leksikografski poredak dvaju rasporeda određuje prvo mjesto na kojem njihovi elementi nisu ekvivalentni prema korištenoj usporedbi. Preopterećenje bez comp koristi zadanu usporedbu „manje od”; preopterećenje s comp određuje poredak pomoću tog komparatora.

Rezultat true znači da je pronađen sljedeći raspored. Rezultat false ne znači da su podaci ostali nepromijenjeni: algoritam obnavlja prvi raspored, sortiran uzlazno prema korištenoj usporedbi. Prazan raspon ili raspon s jednim elementom vraća false.

Iteratori moraju biti dvosmjerni, a elementi na koje upućuju moraju podržavati zamjenu vrijednosti. comp mora definirati strogi slabi poredak; nemojte upotrebljavati <=. Za N elemenata standard ograničava broj zamjena na N / 2.

Počnite s rasponom sortiranim prema istoj usporedbi i upotrijebite do–while kako biste obradili i početni raspored. Petlja prolazi po jedan raspored za svaki različit niz klasa ekvivalencije određenih usporedbom. Ako usporedba smatra različite vrijednosti ekvivalentnima, petlja može preskočiti neke različite nizove vrijednosti. U primjeru zadana usporedba razlikuje 1 i 2, pa petlja ispisuje sva tri različita rasporeda vrijednosti. Primjer prikazuje i stanje nakon posljednjeg poziva koji vraća false.

Primjeri

#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

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

Izvori