I. IntroductionAprès les combinaisons, on s'intéresse cette fois à un algorithme itératif pour générer tous les arrangements de p éléments parmi n.
Il va nous permettre ensuite d'implémenter une fonction en Python qui pourra générer un grand nombre d'arrangements sans avoir besoin de les stocker en mémoire.
L'objectif est toujours 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 arrangements
Si on souhaite par exemple obtenir toutes les façons de tirer successivement 3 boules parmi 4 en tenant compte de l'ordre du tirage, il nous faut tout d'abord numéroter dans l'ordre les 4 boules de la manière suivante :
(0,1,2,3)
On fait commencer les indices des boules à 0 comme pour les indices des tuples en Python.
Et si maintenant on tire successivement les 3 premières boules dans l'ordre, on obtient un arrangement sous forme de tuple, contenant leurs indices respectifs :
(0,1,2)
Mais comme l'ordre du tirage est maintenant pris en compte, choisir (0,1,2) est différent de 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, i0≠i2 et i1≠i2
On encore, si on souhaite indiquer qu'il s'agit de l'arrangement de rang j :
(ij,0,ij,1,ij,2) avec ij,0≠ij,1, ij,0≠ij,2 et ij,1≠ij,2.
Tableau des arrangements et règles de passage entre 2 séquences d'indices successives :
ij,k désignant l'indice k de l'arrangement j.
Dans le cas général, l'arrangement de la ligne j de p boules parmi n peut donc s'écrire sous forme de tuple :
(ij,0, ij,1,.., ij,k-1, ij,k, ij,k+1,.., ij,p-1) chaque indice étant unique (pas de doublon).
On aura alors des tirages qui s'étalent de (0,1,..,k,..,p-1) à ((n-1),(n-2),..,(n-k-1),..,n-p).
On cherchera donc le 1er indice ij,k en partant de la droite qui puisse être incrémenté tout en restant différent des indices qui le précèdent (ij,0, ij,1,.., ij,k-1).
On obtient ensuite l'arrangement de la ligne j+1 représenté sous forme de tuple :
(ij,0, ij,1,.., ij,k-1, ij+1,k, ij+1,k+1,.., ij+1,p-1) chaque indice étant unique (pas de doublon).
Les k premiers indices ne changent pas par rapport au tuple précédent.
On obtient ij+1,k après avoir incrémenté ij,k.
ij+1,k étant le plus petit indice supérieur à ij,k et différent des indices qui le précèdent
Sans oublier bien sûr de réinitialiser aussi les indices suivants pour un prochain cycle :
- ij+1,k+1 est le plus petit indice supérieur ou égal à 0 et différent des indices qui le précèdent.
- ij+1,k+2 est le plus petit indice supérieur à ij+1,k+1 et différent des indices qui le précèdent.
- ij+1,k+3 est le plus petit indice supérieur à ij+1,k+2 et différent des indices qui le précèdent.
- etc..
Toutes les séquences d'indices qui comportent des doublons seront donc ignorées au cours de la procédure.
III. Fonctions itératives en Python
Nous utilisons l'instruction yield qui permet de parcourir l'ensemble des arrangements, sans avoir besoin de les stocker en mémoire :
| 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 29 30 | def arrangements_v1(p,n): if p>n: return indices=list(range(p)) # on initialise la liste des indices [0,1,2,..,p-1] yield tuple(indices) # ordre pour générer le tuple i=p-1 # on part de la fin de la liste des indices k=p # variable utilisé pour incrémenter ou initialiser les indices while i!=-1: # on parcourt les indices de la droite vers la gauche : p-1 -> 0 if k < n: # si la valeur d'indice maxi n'a pas été dépassée if k not in indices[:i]: # si l'indice k n'est pas présent parmi les indices précédant indices[i] indices[i]=k # on incrémente indices[i] avec la valeur de k k=0;j=i+1 # on met k à 0 pour ensuite initialiser les prochains indices : nouveau cycle (ex. : 0,1,2,..). while (j < p): # on parcourt les prochains indices if k not in indices[:i+1]: # si l'indice k n'est pas présent parmi les indices précédant indices[i+1] indices[j]=k # on initialise indices[j] avec la valeur de k j+=1 # prochain indice k+=1 yield tuple(indices) # ordre pour générer le tuple i=p-1 # on revient sur le dernier indice à incrémenter k=indices[i] k+=1 # on incrémente k else: # sinon i-=1 # on remonte les indices vers la gauche k=indices[i]+1 # on met à jour k pour le prochain indice return |
Exemple de code permettant de générer les arrangements de 9 éléments parmi 14 :
| Code Python : | Sélectionner tout |
1 2 3 4 5 | iterator = arrangements_v1(9,14) # on génère les arrangements dans une boucle for a in iterator: # faire quelque chose avec l'arrangement a |
Une version pour générer des arrangements 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 29 30 31 32 | def arrangements_v2(p,e): n=len(e) # longueur de la liste de caractères if p>n: return indices=list(range(p)) # on initialise la liste des indices [0,1,2,..,p-1] yield tuple(e[i] for i in indices) # ordre pour générer le tuple i=p-1 # on part de la fin de la liste des indices k=p # variable utilisé pour incrémenter ou initialiser les indices while i!=-1: # on parcourt les indices de la droite vers la gauche : p-1 -> 0 if k < n: # si la valeur d'indice maxi n'a pas été dépassée if k not in indices[:i]: # si l'indice k n'est pas présent parmi les indices précédant indices[i] indices[i]=k # on incrémente indices[i] avec la valeur de k k=0;j=i+1 # on met k à 0 pour ensuite initialiser les prochains indices : nouveau cycle (ex. : 0,1,2,..). while (j < p): # on parcourt les prochains indices if k not in indices[:i+1]: # si l'indice k n'est pas présent parmi les indices précédant indices[i] indices[j]=k # on initialise indices[j] avec la valeur de k j+=1 # prochain indice k+=1 yield tuple(e[i] for i in indices) # ordre pour générer le tuple i=p-1 # on revient sur le dernier indice à incrémenter k=indices[i] k+=1 # on incrémente k else: # sinon i-=1 # on remonte les indices vers la gauche k=indices[i]+1 # on met à jour k pour le prochain indice return |
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 chacun des arrangements 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 arrangements de p éléments parmi n.