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 );

Transforma el rango [first, last) en la permutación previa. Devuelve true si dicha permutación existe; en caso contrario, transforma el rango en la última permutación (un orden descendente) y devuelve false.

Si el tipo de *first no es Swappable(hasta C++11)BidirIt no es ValueSwappable(desde C++11), el comportamiento no está definido.

Parámetros

Valor de retorno

true si la nueva permutación precede a la anterior en orden lexicográfico. false si se alcanzó la primera permutación y el rango se restableció a la última permutación.

Excepciones

Cualquier excepción lanzada por operaciones de iterador o por el intercambio de elementos.

Complejidad

Dado \(\scriptsize N\)N como std::distance(first, last):

Posible implementación

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;
        }
    }
}

Notas

Promediado sobre toda la secuencia de permutaciones, las implementaciones típicas usan alrededor de 3 comparaciones y 1,5 intercambios por llamada.

Las implementaciones (ej. MSVC STL) pueden habilitar la vectorización cuando el tipo de iterador satisface LegacyContiguousIterator e intercambiar su tipo de valor no invoca ninguna función miembro especial no trivial ni ADL-encontrada swap.

Ejemplo

#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

Véase también