c++ - std:: next_permutation Explicación de la implementación

c++11 stl-algorithm

Question

Tenía curiosidad sobre cómo std:next_permutation se implementó, así que std:next_permutation versión gnu libstdc++ 4.7 y desinfecté los identificadores y el formato para producir la siguiente demo ...

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
        ++i;
        if (i == end)
                return false;

        i = end;
        --i;

        while (true)
        {
                It j = i;
                --i;

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin)
                {
                        reverse(begin, end);
                        return false;
                }
        }
}

int main()
{
        vector<int> v = { 1, 2, 3, 4 };

        do
        {
                for (int i = 0; i < 4; i++)
                {
                        cout << v[i] << " ";
                }
                cout << endl;
        }
        while (::next_permutation(v.begin(), v.end()));
}

El resultado es el esperado: http://ideone.com/4nZdx

Mis preguntas son: ¿Cómo funciona? ¿Cuál es el significado de i , j y k ? ¿Qué valor tienen en las diferentes partes de la ejecución? ¿Qué es un boceto de una prueba de su corrección?

Claramente, antes de ingresar al ciclo principal, simplemente verifica los casos triviales de la lista de elementos 0 o 1. En la entrada del ciclo principal, estoy apuntando al último elemento (no un extremo) y la lista tiene al menos 2 elementos de longitud.

¿Qué está pasando en el cuerpo del ciclo principal?

Answer 1

Aquí hay una implementación completa usando otros algoritmos de biblioteca estándar:

template <typename I, typename C>
    // requires BidirectionalIterator<I> && Compare<C>
bool my_next_permutation(I begin, I end, C comp) {
    auto rbegin = std::make_reverse_iterator(end);
    auto rend = std::make_reverse_iterator(begin);
    auto next_unsorted = std::is_sorted_until(rbegin, rend, comp);
    bool at_final_permutation = (next_unsorted == rend);
    if (!at_final_permutation) {
        auto next_permutation = std::upper_bound(
            rbegin, next_unsorted, *next_unsorted, comp);
        std::iter_swap(next_unsorted, next_permutation);
    }
    std::reverse(rbegin, next_unsorted);
    return !at_final_permutation;
}

Demo

Answer 2

Existe una posible cppreference en cppreference utilizando <algorithm> .

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

Cambia el contenido a la próxima permutación lexicográficamente (en el lugar) y devuelve verdadero si existe, de lo contrario ordena y devuelve falso si no existe.

Answer 3

Knuth profundiza sobre este algoritmo y sus generalizaciones en las secciones 7.2.1.2 y 7.2.1.3 de The Art of Computer Programming . Él lo llama "Algoritmo L", aparentemente se remonta al siglo XIII.

Answer 4

La implementación de gcc genera permutaciones en orden lexicográfico. Wikipedia explica de la siguiente manera:

El siguiente algoritmo genera la siguiente permutación lexicográficamente después de una permutación dada. Cambia la permutación dada en el lugar.

1. Encuentre el índice k más grande de manera que a [k] <a [k + 1]. Si no existe tal índice, la permutación es la última permutación.
2. Encuentre el índice l más grande de manera que a [k] <a [l]. Como k + 1 es dicho índice, l está bien definido y satisface k <l.
3. Cambia un [k] por un [l].
4. Invierta la secuencia de a [k + 1] hasta e incluyendo el elemento final a [n].

Answer 5

Veamos algunas permutaciones:

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
...

¿Cómo pasamos de una permutación a la siguiente? En primer lugar, veamos las cosas de forma un poco diferente. Podemos ver los elementos como dígitos y las permutaciones como números . Viendo el problema de esta manera , queremos ordenar las permutaciones / números en orden "ascendente" .

Cuando ordenamos números, queremos "aumentarlos en la cantidad más pequeña". Por ejemplo, al contar no contamos 1, 2, 3, 10, ... porque todavía hay 4, 5, ... en medio y aunque 10 es más grande que 3, faltan números que pueden obtenerse aumentando 3 por una cantidad menor. En el ejemplo anterior, vemos que 1 mantiene como el primer número durante mucho tiempo, ya que hay muchos reordenamientos de los últimos 3 "dígitos" que "aumentan" la permutación en una cantidad menor.

Entonces, ¿cuándo finalmente "usamos" el 1 ? Cuando solo no hay más permutaciones de los últimos 3 dígitos.
¿Y cuándo no hay más permutaciones de los últimos 3 dígitos? Cuando los últimos 3 dígitos están en orden descendente.

Aha! Esto es clave para entender el algoritmo. Solo cambiamos la posición de un "dígito" cuando todo a la derecha está en orden descendente porque si no está en orden descendente, entonces todavía hay más permutaciones para ir (es decir, podemos "aumentar" la permutación en una cantidad menor) .

Regresemos al código:

while (true)
{
    It j = i;
    --i;

    if (*i < *j)
    { // ...
    }

    if (i == begin)
    { // ...
    }
}

Desde las primeras 2 líneas en el ciclo, j es un elemento y i el elemento anterior.
Luego, si los elementos están en orden ascendente, ( if (*i < *j) ) hace algo.
De lo contrario, si todo está en orden descendente, ( if (i == begin) ) entonces esta es la última permutación.
De lo contrario, continuamos y vemos que j y yo somos esencialmente decrementados.

Ahora comprendemos la parte if (i == begin) por lo que todo lo que necesitamos entender es la parte if (*i < *j) .

También tenga en cuenta: "Entonces, si los elementos están en orden ascendente ...", lo que respalda nuestra observación anterior de que solo necesitamos hacer algo con un dígito "cuando todo a la derecha está en orden descendente". La instrucción de orden ascendente if básicamente busca el lugar más a la izquierda donde "todo a la derecha está en orden descendente".

Veamos nuevamente algunos ejemplos:

...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...

Vemos que cuando todo a la derecha de un dígito está en orden descendente, encontramos el siguiente dígito más grande y lo ponemos al frente y luego ponemos los dígitos restantes en orden ascendente .

Veamos el código:

It k = end;

while (!(*i < *--k))
    /* pass */;

iter_swap(i, k);
reverse(j, end);
return true;

Bueno, como las cosas de la derecha están en orden descendente, para encontrar el "próximo dígito más grande" solo tenemos que iterar desde el final, que vemos en las primeras 3 líneas de código.

Luego, intercambiamos el "próximo dígito más grande" al frente con la declaración iter_swap() y, dado que sabemos que el dígito fue el siguiente más grande, sabemos que los dígitos a la derecha siguen en orden descendente, por lo tanto, iter_swap() orden ascendente, solo tenemos que reverse() .