I. IntroductionL'ensemble des combinaisons de p éléments parmi n peut-être généré en utilisant des fonctions récursives.
Malheureusement ces fonctions ont besoin de plus d'espace mémoire que les fonctions itératives, ce qui peut augmenter nettement le temps d'exécution dans le cas d'un grand nombre d'appels récursifs. C'est pourquoi il vaut mieux en général choisir d'implémenter un algorithme itératif pour ce type de problème.
L'objectif de ce billet est surtout d'expliquer le fonctionnement de ce type d'algorithme sans trop s'attarder sur l'écriture de la fonction en Python.
II. Règles pour représenter et générer ces combinaisons
Si on souhaite par exemple obtenir toutes les façons possibles de tirer 3 boules parmi 6, il nous faut tout d'abord numéroter dans l'ordre les 6 boules de la manière suivante :
(0,1,2,3,4,5)
On fait commencer les indices des boules à 0 comme pour les indices des tuples en Python.
Et si maintenant on choisit par exemple les 3 premières boules, on obtient une combinaison sous forme de tuple, contenant leurs indices respectifs :
(0,1,2)
En effet, choisir (0,1,2) équivaut à choisir (0,2,1) ou (1,0,2) ou (1,2,0) ou (2,0,1) ou (2,1,0).
On représentera alors le tirage de 3 boules quelconques par le tuple :
(i0,i1,i2) avec i0<i1<i2
On gardera donc uniquement les dispositions telles que i0<i1<i2.
Tableau des combinaisons et règles de passage entre 2 séquences d'indices successives :
Donc, dans le cas général une combinaison de p boules parmi n peut s'écrire sous forme de tuple :
(i0, i1,.., ik,.., ip-1) avec i0<i1<..<ik<..<ip-1.
On aura alors des tirages qui s'étalent de (0,1,..,k,..,p-1) à ((n-p),1+(n-p),..,k+(n-p),..,n-1).
On cherchera donc le 1er indice en partant de la droite qui respecte la condition k <= ik < k+(n-p) et qui puisse donc être incrémenté de 1:
ik -> ik+1.
Sans oublier bien sûr de recaler aussi les numéros des boules suivantes en faisant en sorte qu'ils respectent une progression arithmétique de raison 1:
(i0,i1,..,ik+1,ik+2,..,ik+(p-k)) avec i0<i1<..<ik+1<..<ik+(p-k).
Toutes les combinaisons d'indices qui ne respectent pas ces règles seront donc ignorées au cours de la procédure.
III. Fonctions itératives en Python
| Code python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | def combinaisons_v1(p,n): liste_combinaisons=[] # initialisation de la liste des combinaisons à générer indices=list(range(p)) # initialisation de la liste avec les indices de départ [0,1,...,p-1] liste_combinaisons.append(tuple(indices)) # conversion de la liste des indices en tuple puis ajout à la liste des combinaisons if p==n: return liste_combinaisons i = p-1 # on commence à incrémenter le dernier indice de la liste while (i != -1): # tant qu'il reste encore des indices à incrémenter indices[i] += 1 # on incrémente l'indice for j in range(i + 1, p): # on recale les indices des éléments suivants par rapport à ndices[i] indices[j] = indices[j - 1] + 1 if indices[i] == (n - p + i): # si cet indice a atteint sa valeur maxi i -= 1 # on repère l'indice précédent else: # sinon i = p - 1 # on repère le dernier indice liste_combinaisons.append(tuple(indices)) # ajout de la combinaison à la liste return liste_combinaisons |
Cette fonction peut certainement être améliorée.
combinaisons(20,25).
Une version pour générer des combinaisons de caractères alphanumériques :
| Code python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | def combinaisons_v2(p,e): liste_combinaisons=[] # initialisation de la liste des combinaisons à générer n=len(e) # dimension de l'ensemble indices=list(range(p)) # initialisation de la liste avec les indices de départ [0,1,...,p-1] liste_combinaisons.append(tuple([e[index] for index in indices])) # ajout de la combinaison à la liste if p==n: return liste_combinaisons i = p-1 # on commence à incrémenter le dernier indice de la liste while (i != -1): # tant qu'il reste encore des indices à incrémenter indices[i] += 1 # on incrémente l'indice for j in range(i + 1, p): # on recale les indices des éléments suivants par rapport à ndices[i] indices[j] = indices[j - 1] + 1 if indices[i] == (n - p + i): # si cet indice a atteint sa valeur maxi i = i - 1 # on repère l'indice précédent else: # sinon i = p - 1 # on repère le dernier indice liste_combinaisons.append(tuple([e[index] for index in indices])) # ajout de la combinaison à la liste return liste_combinaisons |
combinaisons_v2(3,['a','b','c','d','e']).
Vous trouverez ce type de fonction dans la librairie itertools pour Python.
IV. Conclusion
Après avoir numéroté les n éléments d'un ensemble donné de 0 à n-1, nous avons pu représenter chacune des combinaisons de p éléments pris dans cet ensemble à l'aide de séquences d'indices. Ceci nous a ensuite permis d'identifier certaines règles sur ces séquences. Finalement nous avons pu écrire la fonction permettant de générer dans l'ordre toutes les combinaisons de p éléments parmi n.