CKTIS / C++
std::prev_permutation — předchozí lexikografická permutace
std::prev_permutation přeuspořádá rozsah na jeho předchozí lexikografickou permutaci. Vrací bool; pokud předchozí permutace neexistuje, nastaví poslední permutaci a vrátí false.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
#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 deklarovaná v <algorithm> mění [first, last) přímo a vytvoří bezprostředně předcházející uspořádání v lexikografickém pořadí. O pořadí rozhoduje první pozice, na které hodnoty podle komparátoru nejsou ekvivalentní. V C++23 se k výchozímu porovnávání používá std::less{}, které zaručuje striktní úplné uspořádání ukazatelů i tam, kde je vestavěný operátor < nezaručuje. Přetížení přijímající comp umožňuje zadat jiné striktní slabé uspořádání.
Návratová hodnota true znamená, že byla nalezena předchozí permutace. Hodnota false neznamená, že data zůstala beze změny: algoritmus vytvoří poslední permutaci, tedy sestupné uspořádání podle zvoleného řazení. Pro prázdný rozsah nebo rozsah s jediným prvkem vrátí false a obsah zůstane stejný.
Algoritmus vyžaduje obousměrné iterátory, jejichž odkazované hodnoty lze prohodit. Před provedením jednoho kroku není nutné data řadit. Pokud komparátor rozlišuje každou dvojici různých hodnot v rozsahu, začněte sestupným uspořádáním a použijte cyklus do–while. Tak projdete každé odlišné uspořádání hodnot právě jednou, od největšího po nejmenší. Pokud komparátor považuje různé hodnoty za ekvivalentní, algoritmus rozlišuje pouze uspořádání jejich tříd ekvivalence, takže některá uspořádání hodnot může přeskočit. Pokud například rozsah obsahuje jen dvě různé hodnoty, které jsou podle komparátoru ekvivalentní, už první volání vrátí false.
Příklad ukazuje přechody mezi permutacemi i návrat k poslední permutaci po výsledku false. Tento záznam popisuje přetížení std::prev_permutation, která vracejí bool, nikoli rozhraní std::ranges.
Příklady
#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';
}Výsledek
211 -> true 121 -> true 112 -> false after wrap: 211
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.