Tester chaque combinaison de n éléments sur un ensemble E
Vous êtes ici : Accueil / Articles / Formations en Algorithmique
Cet article est une généralisation de l’article sur les permutations :
Tester chaque permutation sur un ensemble E
En analyse combinatoire, il arrive souvent de devoir tester chacune des permutations sur un ensemble. Nous allons voir comment l’implémenter en C.
Tester toutes les combinaisons de n éléments d’un ensemble E revient à constituer des permutations non finies. ( On s’arrête au nième élément ).
Il existe donc 
combinaisons de n éléments sur E.
Il s’agit donc simplement de changer une des conditions initiales en reprenant l’algorithme précédent :
#define N_ELEMENTS 5
#define CARD_E 10
// Creation des ensembles
void * depart[ CARD_E ];
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 combinaison
...
}
else {
for( i=0; i<CARD_E; i++ ) {
// Insertion de l'element dans l'ensemble d'arrivée
*arrivee = *(depart+i);
// Création de toutes les combinaisons
// 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 );