C++ <algorithme> permutation

Question

Pourquoi cette note de code fonctionne-t-elle (le code se compile et s'exécute bien, mais ne montre pas réellement les permutations) :

int main(int argc, char *argv[])
{
    long number;
    vector<long> interval;
    vector<long>::const_iterator it;

    cout << "Enter number: ";
    cin >> number;

    while(number-->0){
        interval.push_back(number);
    }

    do{
        for(it = interval.begin(); it < interval.end(); ++it){
            cout << *it << " ";
        }
        cout << endl;
    } while(next_permutation(interval.begin(), interval.end()));

    return (0);
}

Mais après avoir changé cette ligne :

while(next_permutation(interval.begin(), interval.end()));

avec :

while(prev_permutation(interval.begin(), interval.end()));

La permutation ne modifie-t-elle pas les éléments du vecteur en agissant sur les positions ?

PS : J'ai modifié le code maintenant.

Answer 1

Les permutations sont ordonné lexicographiquement c'est ce que std::next_permutation y std::prev_permutation les algorithmes traversent.

Ici, vous entrez la permutation la plus "grande", il n'y a donc pas de suivante dans l'ordre.

Answer 2

La permutation ne modifie-t-elle pas les éléments du vecteur en agissant sur les positions ?

Non. next_permutation utilise l'ordre des éléments pour déterminer la permutation suivante.

Par exemple, si A < B < C, alors les next_permutation de [A,B,C] (012) serait [A,C,B] (021). Cependant, si A < C < B, alors la formule next_permutation de [A,B,C] (021) serait [C,A,B] (102).

Puisque votre vecteur était initialement en ordre décroissant, il aurait été la dernière permutation.

Vous pourriez utiliser le std::greater pour inverser le sens de la comparaison.

} while(next_permutation(interval.begin(), interval.end(), greater<long>()));
//                                                         ^^^^^^^^^^^^^^^

Answer 3

Je ne pense pas que next_permutation puisse fonctionner sur les positions (où stockera-t-il cette information ?). Vous devez pouvoir comparer des éléments pour que next_permutation fonctionne, et c'est ce qu'il utilise pour générer la permutation lexicographiquement suivante.

Essayez d'insérer les chiffres dans l'ordre inverse et voyez si cela fonctionne.