CKTIS / C++
std::prev_permutation — vorherige lexikografische Permutation
std::prev_permutation ordnet einen Bereich in seine vorherige lexikografische Permutation um. Die Funktion gibt bool zurück; gibt es keine vorherige Permutation, stellt sie die letzte Permutation her und gibt false zurück.
Version: 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 aus <algorithm> verändert [first, last) direkt und erzeugt die unmittelbar vorherige Anordnung in lexikografischer Reihenfolge. Maßgeblich ist die erste Position, an der die Werte gemäß dem Komparator nicht äquivalent sind. In C++23 wird standardmäßig std::less{} zum Vergleichen verwendet. Damit ist für Zeiger auch dort eine strikte Totalordnung garantiert, wo der eingebaute Operator < keine garantiert. Mit der Überladung, die comp entgegennimmt, lässt sich eine andere strikte schwache Ordnung angeben.
Der Rückgabewert true bedeutet, dass eine vorherige Permutation gefunden wurde. false bedeutet nicht, dass die Daten unverändert bleiben: Der Algorithmus erzeugt die letzte Permutation, also eine absteigende Anordnung gemäß der gewählten Ordnung. Bei einem leeren Bereich oder einem Bereich mit nur einem Element gibt die Funktion false zurück und lässt den Inhalt unverändert.
Erforderlich sind bidirektionale Iteratoren, deren referenzierte Werte vertauscht werden können. Für einen einzelnen Schritt müssen die Daten nicht vorher sortiert werden. Unterscheidet der Komparator jedes Paar verschiedener Werte im Bereich, beginne in absteigender Reihenfolge und verwende eine do–while-Schleife, um jede unterschiedliche Anordnung der Werte genau einmal zu durchlaufen, von der größten zur kleinsten. Gelten verschiedene Werte gemäß dem Komparator als äquivalent, unterscheidet der Algorithmus nur Anordnungen ihrer Äquivalenzklassen und kann daher manche Anordnungen der Werte überspringen. Enthält der Bereich beispielsweise nur zwei verschiedene Werte, die gemäß dem Komparator äquivalent sind, gibt bereits der erste Aufruf false zurück.
Das Beispiel zeigt sowohl die Übergänge zwischen Permutationen als auch den Übergang zur letzten Permutation nach false. Dieser Eintrag behandelt die std::prev_permutation-Überladungen mit Rückgabetyp bool, nicht die Schnittstelle std::ranges.
Beispiele
#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';
}Ergebnis
211 -> true 121 -> true 112 -> false after wrap: 211
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.