Namespaces
Variants

std:: next_permutation

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
next_permutation

C library
Numeric operations
Operations on uninitialized memory
Definiert im 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 ) in die nächste Permutation . Gibt true zurück, falls eine solche "nächste Permutation" existiert; andernfalls transformiert sie den Bereich in die lexikographisch erste Permutation (wie durch std::sort ) und gibt false zurück.

1) Die Menge aller Permutationen ist lexikographisch geordnet bezüglich operator < (bis C++20) std:: less { } (seit C++20) .
2) Die Menge aller Permutationen ist lexikographisch geordnet bezüglich comp .

Wenn der Typ von * first nicht Swappable (bis C++11) BidirIt nicht ValueSwappable (seit C++11) ist, ist das Verhalten undefiniert.

Inhaltsverzeichnis

Parameter

first, last - das Paar von Iteratoren, das den Bereich der zu permutierenden Elemente definiert
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 äquivalent zu folgender sein:

bool cmp ( const Type1 & a, const Type2 & b ) ;

Obwohl die Signatur nicht const & benötigt, darf die Funktion die übergebenen Objekte nicht modifizieren und muss alle Werte des Typs (möglicherweise const) Type1 und Type2 unabhängig von der Wertkategorie akzeptieren können (daher ist Type1 & nicht erlaubt , ebenso wenig wie Type1 , es sei denn, für Type1 ist eine Verschiebung äquivalent zu einer Kopie (seit C++11) ).
Die Typen Type1 und Type2 müssen so beschaffen sein, dass ein Objekt vom Typ BidirIt dereferenziert und dann implizit in beide konvertiert werden kann.

Typanforderungen
-
BidirIt muss die Anforderungen von LegacyBidirectionalIterator erfüllen.

Rückgabewert

true wenn die neue Permutation lexikographisch größer als die alte ist. false wenn die letzte Permutation erreicht wurde und der Bereich auf die erste Permutation zurückgesetzt wurde.

Komplexität

Gegeben N als std:: distance ( first, last ) :

1,2) Höchstens
N
2
Vertauschungen.

Ausnahmen

Alle Ausnahmen, die von Iteratoroperationen oder dem Elementaustausch 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 Vektorisierung ermöglichen, wenn der Iteratortyp LegacyContiguousIterator erfüllt und das Austauschen seines Werttyps weder nicht-triviale spezielle Member-Funktionen noch ADL -gefundene swap -Funktionen aufruft.

Beispiel

Der folgende Code gibt alle drei Permutationen der Zeichenkette "aba" aus.

Diesen Code ausführen 
#include <algorithm>
#include <iostream>
#include <string>
int main()
{
    std::string s = "aba";
    do
    {
        std::cout << s << '\n';
    }
    while (std::next_permutation(s.begin(), s.end()));
    std::cout << s << '\n';
}

Ausgabe: 

aba
baa
aab

Siehe auch

(C++11)
bestimmt, ob eine Sequenz eine Permutation einer anderen Sequenz ist
(Funktions-Template)
erzeugt die nächstkleinere lexikografische Permutation eines Elementbereichs
(Funktions-Template)
(C++20)
erzeugt die nächstgrößere lexikografische Permutation eines Elementbereichs
(Algorithmus-Funktionsobjekt)