CKTIS / C++
std::next_permutation — volgende lexicografische permutatie
std::next_permutation herschikt een bereik naar de volgende lexicografische permutatie. De functie retourneert true als er een volgende permutatie bestaat; na de laatste herstelt ze de eerste rangschikking en retourneert ze false.
Versie: 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 uit <algorithm> wijzigt het bereik [first, last) op zijn plaats. De lexicografische volgorde van twee rangschikkingen wordt bepaald door de eerste positie waarop hun elementen volgens de gekozen vergelijking niet equivalent zijn. De overload zonder comp gebruikt de standaardvergelijking kleiner-dan; de overload met comp bepaalt de volgorde met die comparator.
Een resultaat true betekent dat er een volgende rangschikking is gevonden. Een resultaat false betekent niet dat de gegevens ongewijzigd zijn gebleven: het algoritme herstelt de eerste rangschikking, gesorteerd in oplopende volgorde volgens de gekozen vergelijking. Voor een leeg bereik of een bereik met één element retourneert de functie false.
De iterators moeten bidirectioneel zijn en de elementen waarnaar ze verwijzen moeten het verwisselen van waarden ondersteunen. comp moet een strikte zwakke ordening definiëren; gebruik geen <=. Voor N elementen beperkt de standaard het aantal verwisselingen tot N / 2.
Begin met een bereik dat volgens dezelfde vergelijking is gesorteerd en gebruik do–while, zodat ook de beginrangschikking wordt verwerkt. De lus doorloopt één rangschikking voor elke verschillende reeks van equivalentieklassen die door de vergelijking worden bepaald. Als de vergelijking ongelijke waarden als equivalent beschouwt, kan de lus sommige verschillende waardereeksen overslaan. In het voorbeeld maakt de standaardvergelijking onderscheid tussen 1 en 2, dus drukt de lus alle drie de verschillende rangschikkingen van de waarden af. Het voorbeeld toont ook de toestand na de laatste aanroep die false retourneert.
Voorbeelden
#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';
}
Resultaat
1 1 2 1 2 1 2 1 1 reset: 1 1 2
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.