CKTIS / C++
std::prev_permutation — vorige lexicografische permutatie
std::prev_permutation herschikt een bereik naar de vorige lexicografische permutatie. De functie retourneert bool; als er geen vorige permutatie bestaat, maakt ze de laatste permutatie en retourneert ze false.
Versie: 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, gedeclareerd in <algorithm>, wijzigt [first, last) ter plekke en maakt de direct voorafgaande rangschikking in lexicografische volgorde. De eerste positie waarop de waarden volgens de comparator niet equivalent zijn, bepaalt de volgorde. In C++23 wordt standaard std::less{} gebruikt voor de vergelijking. Die garandeert een strikte totale ordening voor pointers, ook waar de ingebouwde operator < die niet garandeert. Met de overload die comp ontvangt, kun je een andere strikte zwakke ordening opgeven.
Een retourwaarde true betekent dat er een vorige permutatie is gevonden. false betekent niet dat de gegevens ongewijzigd zijn gebleven: het algoritme maakt de laatste permutatie, aflopend volgens de gekozen ordening. Voor een leeg bereik of een bereik met één element retourneert het false en blijft de inhoud gelijk.
Het algoritme vereist bidirectionele iterators waarvan de gerefereerde waarden verwisselbaar zijn. Je hoeft de gegevens niet eerst te sorteren om één stap uit te voeren. Als de comparator elk paar verschillende waarden in het bereik onderscheidt, begin dan in aflopende volgorde en gebruik een do–while-lus om elke verschillende rangschikking van de waarden precies één keer te doorlopen, van groot naar klein. Als verschillende waarden volgens de comparator equivalent zijn, onderscheidt het algoritme alleen rangschikkingen van hun equivalentieklassen en kan het dus sommige rangschikkingen van de waarden overslaan. Bevat het bereik bijvoorbeeld alleen twee verschillende waarden die volgens de comparator equivalent zijn, dan retourneert de eerste aanroep al false.
Het voorbeeld laat zowel de overgangen tussen permutaties als de terugkeer naar de laatste permutatie na false zien. Dit artikel beschrijft de std::prev_permutation-overloads die bool retourneren, niet de std::ranges-interface.
Voorbeelden
#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';
}Resultaat
211 -> true 121 -> true 112 -> false after wrap: 211
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.