std:: prev_permutation

Transformiert den Bereich [ first , last ) in die vorherige Permutation . Gibt true zurück, falls eine solche Permutation existiert, andernfalls wird der Bereich in die letzte Permutation transformiert (wie durch std::sort gefolgt von std::reverse ) und gibt false zurück.

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

Parameter

Rückgabewert

true wenn die neue Permutation der alten in lexikographischer Ordnung vorausgeht. false wenn die erste Permutation erreicht wurde und der Bereich auf die letzte Permutation zurückgesetzt wurde.

Ausnahmen

Alle Ausnahmen, die von Iterator-Operationen oder dem Elementaustausch ausgelöst werden.

Komplexität

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

Mögliche Implementierung

template<class BidirIt>
bool prev_permutation(BidirIt first, BidirIt last)
{
    if (first == last)
        return false;
    BidirIt i = last;
    if (first == --i)
        return false;
    while (1)
    {
        BidirIt i1, i2;
        i1 = i;
        if (*i1 < *--i)
        {
            i2 = last;
            while (!(*--i2 < *i))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

`-Tags wurde gemäß den Anweisungen nicht übersetzt, da er Code darstellt und C++-spezifische Begriffe enthält. Die HTML-Struktur und Attribute bleiben ebenfalls unverändert.

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 Vertauschen seines Werttyps weder nicht-triviale spezielle Memberfunktionen noch ADL -gefundene swap -Funktionen aufruft.

Beispiel

#include <algorithm>
#include <iostream>
#include <string>
int main()
{
    std::string s = "cab";
    do
    {
        std::cout << s << ' ';
    }
    while (std::prev_permutation(s.begin(), s.end()));
    std::cout << s << '\n';
}

cab bca bac acb abc cba

Siehe auch