CKTIS / C++
std::next_permutation — następna permutacja leksykograficzna
std::next_permutation przestawia elementy zakresu na następną permutację w porządku leksykograficznym. Zwraca true po znalezieniu następnej, a po ostatniej przywraca pierwszy układ i zwraca false.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
#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> modyfikuje zakres [first, last) w miejscu. O porządku leksykograficznym dwóch układów decyduje pierwsza pozycja, na której elementy nie są równoważne według użytego porównania. Przeciążenie bez comp używa domyślnego porównania „mniejsze niż”; przeciążenie z comp ustala porządek za pomocą tego komparatora.
Wynik true oznacza znalezienie kolejnego układu. Wynik false nie oznacza pozostawienia danych bez zmian: algorytm przywraca pierwszy układ, uporządkowany rosnąco względem użytego porównania. Dla pustego zakresu lub jednego elementu zwraca false.
Iteratory muszą być dwukierunkowe, a wskazywane elementy muszą umożliwiać zamianę wartości. comp musi definiować ścisły słaby porządek; nie używaj <=. Dla N elementów standard ogranicza liczbę zamian do N / 2.
Zacznij od zakresu posortowanego według tego samego porównania i użyj do–while, aby przetworzyć także początkowy układ. Pętla odwiedza po jednym układzie dla każdej odrębnej sekwencji klas równoważności wyznaczonych przez porównanie. Jeśli porównanie uznaje różne wartości za równoważne, pętla może pominąć niektóre różne sekwencje wartości. W przykładzie domyślne porównanie rozróżnia 1 od 2, więc pętla wypisuje wszystkie trzy różne układy wartości. Przykład pokazuje też stan po końcowym wywołaniu zwracającym false.
Przykłady
#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';
}
Wynik
1 1 2 1 2 1 2 1 1 reset: 1 1 2
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.