Manipulation de données - Réorganisation : rotation et permutati
Réorganisation : rotation et permutation
La bibliothèque standard fournit plusieurs algorithmes permettant de réorganiser la séquence des éléments dans un conteneur qui ne prend pas en charge lui-même l’ordre de ses éléments. Ces algorithmes permettent de réaliser des rotations et des permutations des éléments, des symétries et des inversions, ainsi que des mélanges aléatoires.Les algorithmes de rotation permettent de faire tourner les différents éléments d’une séquence dans un sens ou dans l’autre. Les algorithmes de rotation prennent en argument un itérateur qui indique le premier élément de la séquence devant subir la rotation, un itérateur référençant l’élément qui se trouvera en première position après la rotation, et un itérateur référençant l’élément suivant le dernier élément de la séquence.
Ainsi, pour effectuer une rotation d’une position vers la gauche, il suffit d’utiliser pour l’itérateur pivot la valeur de l’itérateur suivant l’itérateur premier et, pour effectuer une rotation d’une position vers la droite, il faut prendre pour l’itérateur pivot la valeur précédant celle de l’itérateur dernier.
rotate et rotate_copy
Voici la déclaration dans la STL :template <class ForwardIterator>
void rotate(ForwardIterator premier, ForwardIterator pivot,
ForwardIterator dernier);
template <class ForwardIterator, class OutputIterator>
void rotate_copy(ForwardIterator premier, ForwardIterator pivot,
ForwardIterator dernier, OutputIterator destination);
Code 9.5 : algorithme de rotation
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int tab[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
cout << "Voici le tableau initial: \n";
for (int i=0; i<10; i++)
cout << tab[i] << " ";
cout << endl;
//On effectue une rotation pour amener le quatrième
// élément en première position :
rotate(tab, tab+3, tab+10);
cout << "Voici le tableau après rotation: \n";
for (int i=0; i<10; i++)
cout << tab[i] << " ";
cout << endl;
}
La bibliothèque fournit également des algorithmes permettant d’obtenir l’ensemble des permutations d’une séquence d’éléments. Rappelons qu’une permutation est une des combinaisons possibles des valeurs des différents éléments d’un ensemble, en considérant les éléments d’égale valeur comme identiques.
Par exemple, si un ensemble contient deux éléments de même valeur, il n’y a qu’une seule combinaison possible : les deux valeurs. En revanche, si ces deux éléments ont deux valeurs distinctes, on peut réaliser deux combinaisons selon la valeur que l’on place en premier.
next_permutation et prev_permutation
Ces algorithmes prennent tous les deux des itérateurs indiquant les éléments devant subir la permutation et renvoient un booléen indiquant si la permutation suivante ou précédente existe ou non. Si ces permutations n’existent pas, les algorithmes next_permutation et prev_permutation bouclent et calculent respectivement la plus petite et la plus grande permutation de l’ensemble des permutations.Voici la déclaration dans la STL :
template <class BidirectionalIterator> bool next_permutation(BidirectionalIterator premier, BidirectionalIterator dernier); template <class BidirectionalIterator> bool prev_permutation(BidirectionalIterator premier, BidirectionalIterator dernier);
Code 9.6 : algorithme de permutation
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int tab[3] = {1, 1, 2};
//On affiche l’ensemble des permutations de (1, 1, 2) :
do
{
int i;
for (i=0; i<3; i++)
cout << tab[i] << " ";
cout << endl;
}
while (next_permutation(tab, tab+3));
}
Le texte original de cette fiche pratique est extrait de
«Tout sur le C++» (Christine EBERHARDT, Collection
CommentCaMarche.net, Dunod, 2009)