std :: next_permutation Implementation Explanation

Eu estava curioso para saber como std:next_permutationfoi implementado, então extraí a gnu libstdc++ 4.7versão e limpei os identificadores e a formatação para produzir a seguinte demonstração ...

#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()));
}

A saída é a esperada: http://ideone.com/4nZdx

Minhas perguntas são: Como isso funciona? Qual é o significado de i, je k? Que valor eles têm nas diferentes partes da execução? O que é um esboço de uma prova de sua correção?

Claramente, antes de entrar no loop principal, ele apenas verifica os casos triviais de lista de 0 ou 1 elemento. Na entrada do loop principal, i está apontando para o último elemento (não um fim passado) e a lista tem pelo menos 2 elementos.

O que está acontecendo no corpo do loop principal?

Vejamos algumas permutações:

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
...

Como vamos de uma permutação para a próxima? Em primeiro lugar, vamos ver as coisas de maneira um pouco diferente. Podemos ver os elementos como dígitos e as permutações como números . Vendo o problema desta forma , queremos ordenar as permutações / números em ordem "crescente" .

Quando pedimos números, queremos "aumentá-los pelo menor valor". Por exemplo, ao contar, não contamos 1, 2, 3, 10, ... porque ainda há 4, 5, ... entre e embora 10 seja maior que 3, faltam números que podem ser obtidos por aumentando 3 por um valor menor. No exemplo acima, vemos que 1permanece como o primeiro número por um longo tempo, pois há muitas reordenações dos últimos 3 "dígitos" que "aumentam" a permutação em uma quantidade menor.

Então, quando finalmente "usamos" o 1? Quando não houver mais permutações dos últimos 3 dígitos.
E quando não há mais permutações dos últimos 3 dígitos? Quando os últimos 3 dígitos estão em ordem decrescente.

Aha! Esta é a chave para entender o algoritmo.Nós só mudamos a posição de um "dígito" quando tudo à direita está em ordem decrescente, porque se não estiver em ordem decrescente, então ainda existem mais permutações para ir (ou seja, podemos "aumentar" a permutação em uma quantidade menor) .

Vamos agora voltar ao código:

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

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

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

Das 2 primeiras linhas do loop, jé um elemento e ié o elemento anterior a ele.
Então, se os elementos estiverem em ordem crescente, ( if (*i < *j)) faça algo.
Caso contrário, se tudo estiver em ordem decrescente, ( if (i == begin)) então esta é a última permutação.
Caso contrário, continuamos e vemos que j e i são essencialmente decrementados.

Agora entendemos o if (i == begin) parte, então tudo que precisamos entender é a if (*i < *j)parte.

Observe também: "Então se os elementos estão em ordem crescente ..." o que apóia nossa observação anterior de que só precisamos fazer algo para um dígito "quando tudo à direita está em ordem decrescente". A ordem crescenteif declaração de é essencialmente encontrar o lugar mais à esquerda, onde "tudo à direita está em ordem decrescente".

Vejamos novamente alguns exemplos:

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

Vemos que quando tudo à direita de um dígito está em ordem decrescente, encontramos o próximo dígito maior e o colocamos na frente e, em seguida, colocamos os dígitos restantes em ordem crescente .

Vejamos o código:

It k = end;

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

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

Bem, como as coisas à direita estão em ordem decrescente, para encontrar o "próximo dígito maior" nós apenas temos que iterar a partir do final, que vemos nas primeiras 3 linhas de código.

Em seguida, trocamos o "próximo dígito maior" para a frente com a iter_swap()instrução e, como sabemos que esse dígito foi o próximo maior, sabemos que os dígitos à direita ainda estão em ordem decrescente, portanto, para colocá-lo em ordem crescente, nós apenas temos que fazer reverse()isso.

A implementação do gcc gera permutações em ordem lexicográfica. A Wikipedia explica isso da seguinte maneira:

O algoritmo a seguir gera a próxima permutação lexicograficamente após uma dada permutação. Ele muda a permutação fornecida no local.

1. Encontre o maior índice k tal que a [k] <a [k + 1]. Se esse índice não existir, a permutação é a última permutação.
2. Encontre o maior índice l tal que a [k] <a [l]. Como k + 1 é esse índice, l é bem definido e satisfaz k <l.
3. Troque um [k] por um [l].
4. Inverta a sequência de a [k + 1] até e incluindo o elemento final a [n].

Knuth aprofunda esse algoritmo e suas generalizações nas seções 7.2.1.2 e 7.2.1.3 de The Art of Computer Programming . Ele o chama de "Algoritmo L" - aparentemente, data do século XIII.

Aqui está uma implementação completa usando outros algoritmos de biblioteca padrão:

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 rsorted_end = std::is_sorted_until(rbegin, rend, comp);
    bool has_more_permutations = rsorted_end != rend;
    if (has_more_permutations) {
        auto next_permutation_rend = std::upper_bound(
            rbegin, rsorted_end, *rsorted_end, comp);
        std::iter_swap(rsorted_end, next_permutation_rend);
    }
    std::reverse(rbegin, rsorted_end);
    return has_more_permutations;
}

Demo

Há uma implementação possível autoexplicativa no uso de cppreference<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;
        }
    }
}

Altere o conteúdo para a próxima permutação lexicograficamente (no local) e retorne verdadeiro se existir, caso contrário, classifique e retorne falso se não existir.