std::next_permutation

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

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

Permuta el rango [first, last) en la siguiente permutación. Devuelve true si existe dicha "siguiente permutación"; en caso contrario, transforma el rango en la primera permutación lexicográfica (un orden ascendente) 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 es lexicográficamente mayor que la anterior. false si se alcanzó la última permutación y el rango se restableció a la primera permutación.

Complejidad

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

Excepciones

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

Posible implementación

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

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

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

Ejemplo

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>

int main()
{
    std::string s = "ABBA";
    std::sort(s.begin(), s.end());
    
    do
        std::cout << s << '\n';
    while (std::next_permutation(s.begin(), s.end()));

    assert(std::is_sorted(s.begin(), s.end()));
}

AABB
ABAB
ABBA
BAAB
BABA
BBAA

Véase también