Tester chaque permutation sur un ensemble E
Vous êtes ici : Accueil / Articles / Formations en Algorithmique
En analyse combinatoire, il arrive souvent de devoir tester chacune des permutations sur un ensemble. Nous allons voir comment l’implémenter en C.
Qu’est-ce qu’une permutation ?
Une permutation est une bijection d’un ensemble sur lui-même.
Qu’est-ce qu’une bijection ?
Une bijection est une application à la fois injective et surjective.
Qu’est-ce qu’une injection ?
Oh et puis zut..
Une approche intuitive
Nous disposons d’un ensemble fini de n éléments et voulons remplir un autre ensemble disposant de la même capacité. L’algorithme va avoir pour but de le remplir de toutes les manières différentes.
A la première place, nous aurons le choix de placer n éléments. Une fois ce premier élément placé, il nous reste n-1 éléments. Nous aurons donc n-1 choix pour la seconde place, pour chaque occurrence du premier élément, et ainsi de suite.
Le nombre de permutations possibles est de n !.
Il s’agit de trouver un algorithme simple permettant de créer ces permutations.
L’algorithme de backtracking
Un algorithme tout à fait approprié est celui du retour sur trace ( backtracking en Anglais ). En effet, il suit exactement le schéma de la pensée lorsque nous évaluons le nombre de combinaisons possibles.
Il consiste à affecter chaque élément de l’ensemble de départ au premier élément de l’ensemble d’arrivée, et pour chaque occurrence, il teste toutes les permutations sur le sous-ensemble constitué de l’ensemble de départ moins l’élément précédent.
Comme vous le voyez, l’algorithme de backtracking est un algorithme basé sur la recursion.
Implémentation en C
#define N_ELEMENTS 5
// Creation des ensembles
void * depart[ N_ELEMENTS ];
void * arrivee[ N_ELEMENTS ];
void backtracking( void ** depart, int n, void ** arrivee ) {
int i;
// Si l'ensemble d'arrivée est remplis
if( n == 0 ) {
// Se repositionner au debut du tableau
arrivee -= N_ELEMENTS;
// Code à exécuter pour chaque permutation
...
}
else {
for( i=0; i<N_ELEMENTS; i++ ) {
// Ajout de l'élément dans l'ensemble d'arrivée
*arrivee = *(depart+i);
// Création de toutes les permutations
// Sur le sous-ensemble
backtracking( depart+1, n-1, arrivee+1 );
}
}
}
// Initialisation de l'ensemble de départ
....
// Exécution de l'algorithme
backtracking( depart, N_ELEMENTS, arrivee );