std::next_permutation
| Definiert in Header <algorithm>
|
||
template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last );
|
(1) | (constexpr seit C++20) |
template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );
|
(2) | (constexpr seit C++20) |
Permutiert den Bereich [first, last) zur nächsten Permutation. Gibt true zurück, wenn eine solche "nächste Permutation" existiert; andernfalls wird der Bereich in die lexikografisch erste Permutation (aufsteigende Reihenfolge) umgewandelt und false zurückgegeben.
operator<(bis C++20)std::less{}(seit C++20).comp.Wenn der Typ von *first nicht Swappable(bis C++11)BidirIt nicht ValueSwappable(seit C++11) ist, ist das Verhalten undefiniert.
Parameter
| first, last | - | das Paar von Iteratoren, die den Bereich der zu permutierenden Elemente definieren |
| comp | - | Vergleichsfunktionsobjekt (d.h. ein Objekt, das die Anforderungen von Compare erfüllt), das true zurückgibt, wenn das erste Argument kleiner als das zweite ist.Die Signatur der Vergleichsfunktion sollte der folgenden entsprechen:
Während die Signatur |
| Typanforderungen | ||
-BidirIt muss die Anforderungen von LegacyBidirectionalIterator erfüllen.
| ||
Rückgabewert
truewenn die neue Permutation lexikografisch größer als die alte ist. falsewenn die letzte Permutation erreicht wurde und der Bereich auf die erste Permutation zurückgesetzt wurde.
Komplexität
Gegeben N als std::distance(first, last):
| N |
| 2 |
Ausnahmen
Alle Ausnahmen, die von Iteratoroperationen oder Elementvertauschungen ausgelöst werden.
Mögliche Implementierung
template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
auto r_first = std::make_reverse_iterator(last);
auto r_last = std::make_reverse_iterator(first);
auto left = std::is_sorted_until(r_first, r_last);
if (left != r_last)
{
auto right = std::upper_bound(r_first, left, *left);
std::iter_swap(left, right);
}
std::reverse(left.base(), last);
return left != r_last;
}
|
Hinweise
Im Durchschnitt über die gesamte Sequenz von Permutationen verwenden typische Implementierungen etwa 3 Vergleiche und 1,5 Vertauschungen pro Aufruf.
Implementierungen (z.B. MSVC STL) können die Vektorisierung aktivieren, wenn der Iteratortyp LegacyContiguousIterator erfüllt und das Vertauschen seines Werttyps weder eine nicht-triviale spezielle Memberfunktion noch ADL-gefundenes swap aufruft.
Beispiel
Der folgende Code gibt alle Permutationen einer Zeichenkette aus.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
int main()
{
std::string s = "ABBA";
std::sort(s.begin(), s.end());
do
std::cout << s << '\n';
while (std::next_permutation(s.begin(), s.end()));
assert(std::is_sorted(s.begin(), s.end()));
}
Ausgabe:
AABB
ABAB
ABBA
BAAB
BABA
BBAA
Siehe auch
(C++11) |
bestimmt, ob eine Sequenz eine Permutation einer anderen Sequenz ist (Funktionsvorlage & Algorithmus-Funktionsobjekt) |
(C++20) |
|
| erzeugt die nächstkleinere lexikografische Permutation eines Bereichs von Elementen (Funktionsvorlage & Algorithmus-Funktionsobjekt) | |
(C++20) |
|
(C++20) |
erzeugt die nächstgrößere lexikografische Permutation eines Bereichs von Elementen (Algorithmus-Funktionsobjekt) |