std::prev_permutation

template< class BidirIt >
bool prev_permutation( BidirIt first, BidirIt last );

template< class BidirIt, class Compare >
bool prev_permutation( BidirIt first, BidirIt last, Compare comp );

Transformiert den Bereich [first, last) in die vorherige Permutation. Gibt true zurück, falls eine solche Permutation existiert, andernfalls transformiert es den Bereich in die letzte Permutation (eine absteigende Reihenfolge) und gibt false zurück.

Falls 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 lexikografischer Ordnung vorausgeht. false, wenn die erste Permutation erreicht wurde und der Bereich auf die letzte Permutation zurückgesetzt wurde.

Ausnahmen

Jegliche Ausnahmen, die von Iteratoroperationen oder dem Elementtausch 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;
        }
    }
}

Hinweise

Über die gesamte Sequenz von Permutationen gemittelt, 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

#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