CKTIS / C++
std::next_permutation — nasledujúca lexikografická permutácia
std::next_permutation preusporiada rozsah na jeho nasledujúcu lexikografickú permutáciu. Vráti true, ak existuje ďalšia permutácia; po poslednej obnoví prvé usporiadanie a vráti false.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
#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 z <algorithm> priamo mení rozsah [first, last). O lexikografickom poradí dvoch usporiadaní rozhoduje prvá pozícia, na ktorej ich prvky nie sú podľa použitého porovnania ekvivalentné. Preťaženie bez comp používa predvolené porovnanie „menší ako“; preťaženie s comp určuje poradie pomocou tohto komparátora.
Výsledok true znamená, že sa našlo nasledujúce usporiadanie. Výsledok false neznamená, že údaje zostali nezmenené: algoritmus obnoví prvé usporiadanie, zoradené vzostupne podľa použitého porovnania. Prázdny rozsah alebo rozsah s jediným prvkom vráti false.
Iterátory musia byť obojsmerné a prvky, na ktoré odkazujú, musia umožňovať výmenu hodnôt. comp musí definovať striktné slabé usporiadanie; nepoužívajte <=. Pre N prvkov štandard obmedzuje počet výmen na N / 2.
Začnite rozsahom zoradeným podľa toho istého porovnania a použite do–while, aby sa spracovalo aj počiatočné usporiadanie. Cyklus prejde jedno usporiadanie pre každú odlišnú postupnosť tried ekvivalencie určených porovnaním. Ak porovnanie považuje rôzne hodnoty za ekvivalentné, cyklus môže niektoré odlišné postupnosti hodnôt preskočiť. V príklade predvolené porovnanie rozlišuje 1 a 2, takže cyklus vypíše všetky tri rôzne usporiadania hodnôt. Príklad ukazuje aj stav po záverečnom volaní, ktoré vráti false.
Príklady
#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';
}
Výsledok
1 1 2 1 2 1 2 1 1 reset: 1 1 2
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.