Comme j'ai vu pas mal de fois le problème de la détermination des combinaisons de n chiffres ou de n caractères par exemple, je propose un ajout sur ça.
On va donner un algorithme qui va permettre de donner les combinaisons de n caractères d'une liste de symbole (par exemple 0 à 9 ou c à f). Comme justement ces symboles peuvent être particuliers, on peut définir un Type et leur attribuer 3 fonctions.
- init() qui retourne le plus petit symbole (par exemple 0 pour les chiffres)
- suivant(Type t) retourne le symbole suivant (par exemple suivant(0) = 1 ou suivant(b) = c)
- estALaLimite(Type t) qui retourne vrai si le symbole est à la limite des symboles que l'on souhaite (par exemple 9 pour les chiffres de 0 à 9, ou g pour les caractères de b à g.
On considère un tableau de taille n d'un certain Type, et on va déterminer toutes les combinaisons possibles de n caractères en les inscrivant dans ce tableau.
Une manière de faire et d'imaginer que l'on a affaire à une recherche de combinaisons de chiffre (par exemple les combinaisons de 4 caractères utilisant les chiffres de 0 à 9). On voit bien que pour passer q'une combinaison (par exemple 1239) à l'autre, on peut ajouter 1 (1240). On va utiliser ce principe pour générer toutes les combinaisons en effectuant une retenue si nécessaire.
Ensuite, pour tous les obtenir, il suffit d'appeler genererSuivant tant que l'on souhaite et initialiser le tableau avec init() au début
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 /* T correspond au tableau et k à la position de la retenue*/ Procédure evoluerRetenue(Permutation T, Entier k) T[k] <- init() Si estALaLimite(T[k+1]) Si k+1>n alors c'est fini Sinon evaluerRetenue(T,k+1) Sinon T[k+1] <- suivant(T[k+1]) /*Prend une combinaison dans un tableau T, et génère le suivant*/ Procédure genererSuivant(Permutation T) Si estALaLimite(T[1]) evoluerRetenue(T,1) Sinon T[1] <- suivant(T[1])
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 Pour i = 1 à n T[i] <- init() Tant que l'on a pas fini genererSuivant(T) ... faire ce qu' l'on doit faire avec la combinaisons
À noter que la procédure evoluerRetenue est terminale récursive, on peut facilement utiliser une simple boucle tant que.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 Procédure evoluerRetenue(Permutation T, k) Tant que estALaLimite(T[k]) T[k] <- init() k++ T[k] <- suivant(T[k])
------------------------------------------------------------------
Typiquement pour des chiffres de 0 à 9, on peut définir les fonctions init, suivant et estALaLimite comme suit.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 fonction init() -> Entier Retourne 0 fonction suivant(Entier i) -> Entier Retourne i+1 //normalement, ne doit pas être appelé au cas limite fonction estALaLimite(Entier i) -> Booléen Retourne i==9
Par Florent Humbert
Si vous avez une autre méthode qui marche dans le cas général, n'hésitez pas.
Partager