Oui, il y a est un algorithme de "permutation suivante", et c'est aussi très simple. La bibliothèque standard de modèles C++ (STL) possède même une fonction appelée next_permutation .
L'algorithme trouve en fait le suivant la permutation -- celle qui est lexicographiquement la plus proche. L'idée est la suivante : supposons que l'on vous donne une séquence, disons "32541". Quelle est la permutation suivante ?
Si vous y réfléchissez, vous verrez que c'est "34125". Et vos pensées étaient probablement quelque chose comme ça : Dans "32541",
- il n'y a aucun moyen de garder le "32" fixe et de trouver une permutation ultérieure dans la partie "541", car cette permutation est déjà la dernière pour 5,4 et 1 -- elle est triée par ordre décroissant.
- Vous devrez donc remplacer le "2" par quelque chose de plus grand -- en fait, par le plus petit nombre plus grand que lui dans la partie "541", à savoir 4.
- Maintenant, une fois que vous avez décidé que la permutation commencera par "34", le reste des nombres devrait être dans l'ordre croissant, la réponse est donc "34125".
L'algorithme vise à mettre en œuvre précisément ce raisonnement :
- Trouvez la plus longue "queue" qui est classée par ordre décroissant. (La partie "541".)
- Changez le nombre juste avant la queue (le "2") en le plus petit nombre plus grand que lui dans la queue (le 4).
- Trier la queue par ordre croissant.
Vous pouvez réaliser (1.) efficacement en commençant par la fin et en revenant en arrière, tant que l'élément précédent n'est pas plus petit que l'élément actuel. Pour réaliser l'étape (2.), il suffit de remplacer le "4" par le "2", ce qui donne "34521". Une fois que vous avez fait cela, vous pouvez éviter d'utiliser un algorithme de tri pour (3.), parce que la queue était, et est toujours (pensez-y), triée par ordre décroissant, donc il suffit de l'inverser.
C'est précisément ce que fait le code C++ (voir le code source dans la section /usr/include/c++/4.0.0/bits/stl_algo.h sur votre système, ou voir cet article ) ; il devrait être simple de le traduire dans votre langue : [Lire "BidirectionalIterator" comme "pointeur", si vous n'êtes pas familier avec les itérateurs C++. Le code renvoie false s'il n'y a pas de permutation suivante, c'est-à-dire que nous sommes déjà en ordre décroissant].
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator i = first;
++i;
if (i == last) return false;
i = last;
--i;
for(;;) {
BidirectionalIterator ii = i--;
if (*i <*ii) {
BidirectionalIterator j = last;
while (!(*i <*--j));
iter_swap(i, j);
reverse(ii, last);
return true;
}
if (i == first) {
reverse(first, last);
return false;
}
}
}
Il peut sembler que cela puisse prendre O(n) temps par permutation, mais si vous y réfléchissez plus attentivement, vous pouvez prouver que cela prend O(n !) temps pour toutes les permutations au total, donc seulement O(1) -- temps constant -- par permutation.
Ce qui est bien, c'est que l'algorithme fonctionne même lorsque vous avez une séquence avec des éléments répétés : avec, disons, "232254421", il trouverait la queue comme "54421", échangerait le "2" et le "4" (donc "232454221"), inverserait le reste, ce qui donnerait "232412245", qui est la permutation suivante.
