std:: next_permutation

Permuta el rango [ first , last ) a la siguiente permutación . Devuelve true si existe tal "siguiente permutación"; de lo contrario transforma el rango en la primera permutación lexicográfica (como si fuera mediante std::sort ) y devuelve false .

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

Parámetros

Valor de retorno

true si la nueva permutación es lexicográficamente mayor que la anterior. false si se alcanzó la última permutación y el rango se reinició a la primera permutación.

Complejidad

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

Excepciones

Cualquier excepción lanzada desde operaciones de iteradores o el intercambio de elementos.

Implementación posible

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

Notas

Promediado sobre toda la secuencia de permutaciones, las implementaciones típicas utilizan aproximadamente 3 comparaciones y 1.5 intercambios por llamada.

Las implementaciones (por ejemplo, MSVC STL ) pueden habilitar la vectorización cuando el tipo de iterador satisface LegacyContiguousIterator y el intercambio de su tipo de valor no llama ni a funciones miembro especiales no triviales ni a ADL -encontrado swap .

Ejemplo

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

aba
baa
aab

Véase también