Explication de l'implémentation de std :: next_permutation

J'étais curieux de savoir comment cela a std:next_permutationété implémenté, j'ai donc extrait la gnu libstdc++ 4.7version et nettoyé les identifiants et le formatage pour produire la démo suivante ...

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

Le résultat est comme prévu: http://ideone.com/4nZdx

Mes questions sont: comment ça marche? Quel est le sens de i, jet k? Quelle valeur ont-ils aux différentes étapes de l'exécution? Qu'est-ce qu'une esquisse d'une preuve de son exactitude?

Clairement, avant d'entrer dans la boucle principale, il vérifie simplement les cas triviaux de liste d'éléments 0 ou 1. A l'entrée de la boucle principale, je pointe vers le dernier élément (pas une dernière extrémité) et la liste est longue d'au moins 2 éléments.

Que se passe-t-il dans le corps de la boucle principale?

Regardons quelques permutations:

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

Comment passer d'une permutation à l'autre? Tout d'abord, regardons les choses un peu différemment. Nous pouvons voir les éléments sous forme de chiffres et les permutations sous forme de nombres . En regardant le problème de cette manière, nous voulons ordonner les permutations / nombres dans l'ordre "croissant" .

Lorsque nous commandons des numéros, nous voulons "les augmenter du plus petit montant". Par exemple en comptant on ne compte pas 1, 2, 3, 10, ... car il y a encore 4, 5, ... entre et bien que 10 soit plus grand que 3, il manque des nombres qui peuvent être obtenus par augmentant 3 par un montant plus petit. Dans l'exemple ci-dessus, nous voyons que cela 1reste le premier nombre pendant une longue période car il y a beaucoup de réorganisations des 3 derniers "chiffres" qui "augmentent" la permutation d'une quantité plus petite.

Alors, quand enfin «utiliser» le 1? Lorsqu'il n'y a plus de permutations des 3 derniers chiffres.
Et quand n'y a-t-il plus de permutations des 3 derniers chiffres? Lorsque les 3 derniers chiffres sont dans l'ordre décroissant.

Ah! Ceci est essentiel pour comprendre l'algorithme. Nous ne modifions la position d'un "chiffre" que lorsque tout à droite est dans l'ordre décroissant car si ce n'est pas dans l'ordre décroissant, il y a encore plus de permutations à faire (c'est- à- dire que nous pouvons "augmenter" la permutation d'un plus petit montant) .

Revenons maintenant au code:

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

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

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

À partir des 2 premières lignes de la boucle, jest un élément et iest l'élément avant lui.
Ensuite, si les éléments sont dans l'ordre croissant, ( if (*i < *j)) faites quelque chose.
Sinon, si le tout est dans l'ordre décroissant, ( if (i == begin)) alors c'est la dernière permutation.
Sinon, on continue et on voit que j et i sont essentiellement décrémentés.

Nous comprenons maintenant la if (i == begin)partie, donc tout ce que nous devons comprendre est la if (*i < *j)partie.

Notez également: "Alors si les éléments sont dans l'ordre croissant ..." ce qui confirme notre observation précédente que nous n'avons besoin de faire quelque chose qu'à un chiffre "quand tout à droite est dans l'ordre décroissant". L' ifinstruction d' ordre croissant trouve essentiellement l'endroit le plus à gauche où «tout ce qui est à droite est dans l'ordre décroissant».

Regardons à nouveau quelques exemples:

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

Nous voyons que lorsque tout ce qui se trouve à droite d'un chiffre est dans l'ordre décroissant, nous trouvons le chiffre suivant le plus grand et le mettons devant , puis les chiffres restants dans l'ordre croissant .

Regardons le code:

It k = end;

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

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

Eh bien, puisque les choses à droite sont dans l'ordre décroissant, pour trouver le "prochain plus grand chiffre", nous devons juste itérer à partir de la fin, ce que nous voyons dans les 3 premières lignes de code.

Ensuite, nous échangeons le "prochain plus grand chiffre" vers l'avant avec l' iter_swap()instruction et puis, puisque nous savons que ce chiffre était le prochain plus grand, nous savons que les chiffres à droite sont toujours dans l'ordre décroissant, donc pour le mettre dans l'ordre croissant, nous devons juste le faire reverse().

L'implémentation gcc génère des permutations dans l'ordre lexicographique. Wikipédia l' explique comme suit:

L'algorithme suivant génère la permutation lexicographique suivante après une permutation donnée. Il modifie la permutation donnée en place.

1. Trouvez le plus grand indice k tel que a [k] <a [k + 1]. Si un tel indice n'existe pas, la permutation est la dernière permutation.
2. Trouvez le plus grand index l tel que a [k] <a [l]. Puisque k + 1 est un tel indice, l est bien défini et satisfait k <l.
3. Échangez un [k] avec un [l].
4. Inversez la séquence de a [k + 1] jusqu'à et y compris l'élément final a [n].

Knuth approfondit cet algorithme et ses généralisations dans les sections 7.2.1.2 et 7.2.1.3 de The Art of Computer Programming . Il l'appelle "Algorithme L" - apparemment, il remonte au 13ème siècle.

Voici une implémentation complète utilisant d'autres algorithmes de bibliothèque standard:

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

Démo

Il existe une implémentation possible explicite sur cppreference en utilisant <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;
        }
    }
}

Changez le contenu en permutation lexicographique suivante (sur place) et retournez true s'il existe, sinon triez et retournez false s'il n'existe pas.