std::next_permutation Explication de l'implémentation

Question

J'étais curieux de savoir comment std:next_permutation a été mis en œuvre, j'ai donc extrait le gnu libstdc++ 4.7 et a 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 conforme aux attentes : http://ideone.com/4nZdx

Mes questions sont les suivantes : Comment cela fonctionne-t-il ? Quelle est la signification de i , j et k ? Quelle valeur ont-ils aux différents moments de l'exécution ? Qu'est-ce que l'esquisse d'une preuve de sa justesse ?

Il est clair qu'avant d'entrer dans la boucle principale, il ne vérifie que les cas triviaux de liste à 0 ou 1 élément. A l'entrée de la boucle principale, i pointe sur le dernier élément (pas un élément après la fin) et la liste a au moins 2 éléments.

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

Answer 1

Examinons 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 passe-t-on d'une permutation à l'autre ? Tout d'abord, regardons les choses un peu différemment. Nous pouvons considérer les éléments comme des chiffres et les permutations comme des nombres. . En considérant le problème de cette manière nous voulons classer les permutations/numéros dans l'ordre "croissant". .

Lorsque nous ordonnons des nombres, nous voulons les "augmenter de la plus petite quantité". Par exemple, lorsque nous comptons, nous ne comptons pas 1, 2, 3, 10, ... parce qu'il y a toujours 4, 5, ... entre les deux et bien que 10 soit plus grand que 3, il manque des nombres qui peuvent être obtenus en augmentant 3 d'une plus petite quantité. Dans l'exemple ci-dessus, nous voyons que 1 reste longtemps le premier nombre car il existe de nombreuses réorganisations des trois derniers "chiffres" qui "augmentent" la permutation d'une quantité moindre.

Alors quand est-ce qu'on "utilise" enfin le 1 ? Quand il n'y a plus de permutations des 3 derniers chiffres.
Et quand n'y aura-t-il plus de permutations des 3 derniers chiffres ? Quand les 3 derniers chiffres sont dans l'ordre décroissant.

Aha ! C'est la clé pour comprendre l'algorithme. On ne change la position d'un "chiffre" que lorsque tout ce qui est à droite est en ordre décroissant. parce que si ce n'est pas dans l'ordre décroissant, alors il y a encore d'autres permutations à faire. (c'est-à-dire que nous pouvons "augmenter" la permutation d'une plus petite quantité).

Revenons maintenant au code :

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

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

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

A partir des 2 premières lignes de la boucle, j est un élément et i est l'élément qui le précède.
Ensuite, si les éléments sont dans l'ordre croissant, ( if (*i < *j) ) faire 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 le if (i == begin) donc tout ce que nous devons comprendre est le if (*i < *j) partie.

Notez également : "Alors, si les éléments sont dans l'ordre croissant ...", ce qui confirme notre observation précédente selon laquelle nous ne devons faire quelque chose à un chiffre que "lorsque tout ce qui est à droite est dans l'ordre décroissant". L'ordre ascendant if consiste essentiellement à trouver l'endroit le plus à gauche où "tout ce qui est à droite est en ordre décroissant".

Examinons à 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 est à droite d'un chiffre est dans l'ordre décroissant, on trouvez le chiffre le plus grand suivant et mettez-le devant et ensuite mettre 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 simplement itérer à partir de la fin, ce que nous voyons dans les 3 premières lignes de code.

Ensuite, nous intervertissons le "chiffre suivant le plus grand" à l'avant avec la fonction iter_swap() et ensuite, puisque nous savons que ce chiffre était le plus grand suivant, nous savons que les chiffres de droite sont toujours dans l'ordre décroissant, donc pour les mettre dans l'ordre croissant, il suffit de reverse() il.

Answer 2

L'implémentation de gcc génère des permutations par ordre lexicographique. Wikipedia l'explique comme suit :

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

1. Trouver le plus grand indice k tel que a[k] < a[k + 1]. Si un tel indice n'existe pas existe, la permutation est la dernière permutation.
2. Trouver le plus grand indice l tel que a[k] < a[l]. Puisque k + 1 est un tel indice, l est bien d ? bien défini et satisfait k < l.
3. Remplacez a[k] par a[l].
4. Inverser la séquence de a[k + 1] jusqu'à et y compris le dernier élément a[n].

Answer 3

Knuth explique en détail cet algorithme et ses généralisations dans les sections 7.2.1.2 et 7.2.1.3 du document L'art de la programmation informatique . Il l'appelle "Algorithme L". Apparemment, il remonte au 13e siècle.

Answer 4

Voici une implémentation complète utilisant d'autres algorithmes de la 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 rupper_bound = std::upper_bound(
            rbegin, rsorted_end, *rsorted_end, comp);
        std::iter_swap(rsorted_end, rupper_bound);
    }

    std::reverse(rbegin, rsorted_end);
    return has_more_permutations;
}

Démo

Answer 5

Il y a une implémentation possible et explicite sur Référence cpp 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;
        }
    }
}

Change le contenu en permutation lexicographiquement suivante (in-place) et retourne true si elle existe sinon trie et retourne false si elle n'existe pas.