std::prev_permutation

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

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

Transforme la plage [first, last) en la permutation précédente. Renvoie true si une telle permutation existe, sinon transforme la plage en la dernière permutation (un ordre décroissant) et renvoie false.

Si le type de *first n'est pas Swappable(jusqu'à C++11)BidirIt n'est pas ValueSwappable(depuis C++11), le comportement est indéfini.

Paramètres

Valeur de retour

true si la nouvelle permutation précède l'ancienne dans l'ordre lexicographique. false si la première permutation a été atteinte et que la plage a été réinitialisée à la dernière permutation.

Exceptions

Toute exception levée par les opérations d'itérateur ou l'échange d'éléments.

Complexité

Étant donné \(\scriptsize N\)N comme std::distance(first, last) :

Implémentation possible

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

Notes

En moyenne sur toute la séquence des permutations, les implémentations typiques utilisent environ 3 comparaisons et 1,5 échange par appel.

Les implémentations (p. ex. MSVC STL) peuvent activer la vectorisation lorsque le type d'itérateur satisfait LegacyContiguousIterator et que l'échange de son type de valeur n'appelle ni une fonction membre spéciale non triviale ni un swap ADL-trouvé swap.

Exemple

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

int main()
{
    std::string s = "cab";
    
    do
    {
        std::cout << s << ' ';
    }
    while (std::prev_permutation(s.begin(), s.end()));
    
    std::cout << s << '\n';
}

cab bca bac acb abc cba

Voir aussi