I. IntroductionAprès les combinaisons, on s'intéresse maintenant aux arrangements :
L'objectif sera cette fois de créer une fonction récursive en Python qui pourra générer la liste des arrangements de k éléments pris dans un ensemble à n éléments.
On va ensuite montrer comment transformer ce code en une fonction génératrice qui va nous permettre d'obtenir les arrangements sans avoir besoin de les stocker dans une liste.
II. Arrangements
D'après Wikipedia, en analyse combinatoire, le nombre d'arrangements, défini pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, est le nombre de parties ordonnées de k éléments dans un ensemble de n éléments.
Lorsque l'on choisit k objets parmi n objets et que l’ordre dans lequel les objets sont sélectionnés revêt une importance, on peut les représenter par un k-uplet d'éléments distincts et on en constitue une liste ordonnée sans répétition possible, c'est-à-dire dans laquelle l'ordre des éléments est pris en compte (si l'on permute deux éléments de la liste, on a une liste différente, et un élément ne peut être présent qu'une seule fois). Une telle liste ordonnée est un arrangement.
Par exemple, au tiercé, il faut deviner l'ordre d'arrivée des 3 premiers chevaux parmi n au départ. Il y a alors autant de tiercés possibles à l'arrivée que d'arrangements de k=3 éléments pris parmi n.
Autre exemple, dans une assemblée de 30 personnes on doit élire un bureau composé de 4 membres (un président, un vice-président, un secrétaire et un trésorier). Il y a alors autant de bureaux possibles que d'arrangements de 4 éléments pris parmi 30.
Le nombre d'arrangements de k éléments pris dans un ensemble à n éléments est donné par les formules :
On peut remarquer que ce nombre croit rapidement quand k et n augmentent.
III. Génération des arrangements
Prenons par exemple un ensemble à n=4 éléments :
E = {a, b, c, d}
On souhaite obtenir tous les arrangements de k=3 éléments pris dans l'ensemble E, c'est-à-dire générer la liste des triplets :
(a, b, c), (a, b, d), ..., (d, c, b).
On peut dénombrer tous les résultats possibles à l'aide d'un arbre des possibilités :
On a 4 choix possibles (ou branches) au premier niveau, puis 3 choix possibles pour chaque nœud au second niveau, et enfin plus que 2 pour chaque nœud au dernier niveau, ce qui fait donc bien 4×3×2=24 triplets à la fin.
Cet arbre de dénombrement nous permet également de mieux visualiser le processus récursif de génération des arrangements.
Si on voulait par exemple afficher tous les arrangements de k éléments pris dans une liste donnée, on obtiendrait ainsi le pseudo-code récursif :
| Code : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | Algo arrangements(elements, k, arr=()):
Si k=0 alors
afficher(arr)
Sinon
Pour i de 0 jusqu'à longueur(elements)-1
# nouvelle liste d'éléments sans elements[i] (indice débutant à 0 : comme en Python)
new_elements = elements[0:i] + elements[i+1:]
# nouveau tuple avec elements[i] en plus
new_arr = arr + elements[i]
# appel récursif pour k-1
arrangements(new_elements, k-1, new_arr)
Fin pour
Fin si
Fin Algo |
IV. Implémentation en Python
IV-A. Génération des arrangements
On présente maintenant la fonction récursive qui génère la liste contenant les arrangements de k éléments pris dans un ensemble à n éléments :
| 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 | def generer_arrangements(elements, k, arr=()): # fonction permettant de générer la liste des arrangements de k éléments pris dans un ensemble de n éléments # generer_arrangements(['a','b','c'], 2) → ('a','b'), ('a','c'), ('b','a'), ('b','c'), ('c','a'), ('c','b') # si k=0 if k==0: # On renvoie une liste contenant l'arrangement arr. return [arr] else: # sinon # initialisation de la liste des arrangements arrangements = [] # parcours des éléments et de leur indice for i,e in enumerate(elements): # appel récursif pour k-1 : generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,)) # arguments : elements[0:i] + elements[i+1:] → elements, k-1 → k, arr + (e,) → arr arrangements += generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,)) # Renvoie la liste des arrangements. return arrangements |
Testons maintenant la fonction :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 | # valeur de k k = 3 # création de la liste d'éléments elements = ['a','b','c','d'] # Génère la liste des arrangements de k éléments pris dans un ensemble de n éléments. arrangements = generer_arrangements(elements, k) # Affiche la liste des arrangements. print(arrangements) |
Le code affiche :
[('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'b'), ('a', 'c', 'd'), ('a', 'd', 'b'), ('a', 'd', 'c'), ('b', 'a', 'c'), ('b', 'a', 'd'), ('b', 'c', 'a'), ('b', 'c', 'd'), ('b', 'd', 'a'), ('b', 'd', 'c'), ('c', 'a', 'b'), ('c', 'a', 'd'), ('c', 'b', 'a'), ('c', 'b', 'd'), ('c', 'd', 'a'), ('c', 'd', 'b'), ('d', 'a', 'b'), ('d', 'a', 'c'), ('d', 'b', 'a'), ('d', 'b', 'c'), ('d', 'c', 'a'), ('d', 'c', 'b')]
IV-B. Fonction génératrice avec yield et yield from
Comme on l'a vu précédemment, le nombre d'arrangements croît très rapidement quand les paramètres k et n augmentent, ce qui risque d'entrainer des problèmes de mémoire insuffisante (MemoryError, ...).
On peut dans ce cas utiliser à la place une fonction génératrice qui va créer à la demande l'élément suivant de la séquence sans avoir besoin de le stocker dans une liste, permettant ainsi d’économiser de la mémoire.
Pour cela, Python dispose des instructions yield et yield from qui permettent de transformer la fonction récursive précédente en générateur :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def generateur_arrangements(elements, k, arr=()): # fonction permettant de générer tous les arrangements de k éléments pris dans un ensemble de n éléments # generateur_arrangements(['a','b','c'], 2) → ('a','b'), ('a','c'), ('b','a'), ('b','c'), ('c','a'), ('c','b') # si k=0 if k==0: # On génère l'arrangement arr. yield arr else: # sinon # parcours des éléments et de leur indice for i,e in enumerate(elements): # appel récursif pour k-1 : generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,)) : yield from .. # arguments : elements[0:i] + elements[i+1:] → elements, k-1 → k, arr + (e,) → arr yield from generateur_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,)) |
Comme on peut le constater, on utilise l'instruction yield from juste avant l'appel récursif et l'instruction yield pour générer l'arrangement.
L'instruction yield from, apparue avec la version 3.3 de Python, autorise le générateur à déléguer une partie de ses opérations à un autre générateur.
Testons maintenant notre fonction :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # valeur de k k = 3 # création de la liste d'éléments elements = ['a','b','c','d'] # Crée le générateur permettant de parcourir la liste des arrangements de k éléments pris dans un ensemble de n éléments. gen_arrangements = generateur_arrangements(elements, k) print("Liste des arrangements :\n") # parcours des arrangements un à un for arrangement in gen_arrangements: # Affiche l'arrangement. print(arrangement) |
Le code affiche :
Liste des arrangements :
('a', 'b', 'c')
('a', 'b', 'd')
('a', 'c', 'b')
('a', 'c', 'd')
('a', 'd', 'b')
('a', 'd', 'c')
('b', 'a', 'c')
('b', 'a', 'd')
('b', 'c', 'a')
('b', 'c', 'd')
('b', 'd', 'a')
('b', 'd', 'c')
('c', 'a', 'b')
('c', 'a', 'd')
('c', 'b', 'a')
('c', 'b', 'd')
('c', 'd', 'a')
('c', 'd', 'b')
('d', 'a', 'b')
('d', 'a', 'c')
('d', 'b', 'a')
('d', 'b', 'c')
('d', 'c', 'a')
('d', 'c', 'b')
Vous pouvez d'ailleurs retrouver ce type de fonction dans la librairie itertools.
IV-C. Application : tiercés dans l'ordre
On a 4 chevaux au départ d'une course, numérotés de 1 à 4, et on souhaite obtenir tous les tiercés dans l'ordre possibles :
| 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 | # valeur de k k = 3 print("k = " + str(k)) # création de la liste d'éléments : numéros au départ elements = [1, 2, 3, 4] print("E = " + str(elements).replace("[","{").replace("]","}")) print() # Crée le générateur permettant de parcourir la liste des arrangements de k éléments pris dans un ensemble de n éléments gen_arrangements = generateur_arrangements(elements, k) print("Liste des tiercés dans l'ordre possibles :\n") # parcours les arrangements un à un : tiercés possibles for arrangement in gen_arrangements: # Affiche l'arrangement : tiercé possible print(arrangement) |
Le code affiche :
k = 3
E = {1, 2, 3, 4}
Liste des tiercés dans l'ordre possibles :
(1, 2, 3)
(1, 2, 4)
(1, 3, 2)
(1, 3, 4)
(1, 4, 2)
(1, 4, 3)
(2, 1, 3)
(2, 1, 4)
(2, 3, 1)
(2, 3, 4)
(2, 4, 1)
(2, 4, 3)
(3, 1, 2)
(3, 1, 4)
(3, 2, 1)
(3, 2, 4)
(3, 4, 1)
(3, 4, 2)
(4, 1, 2)
(4, 1, 3)
(4, 2, 1)
(4, 2, 3)
(4, 3, 1)
(4, 3, 2)
IV-D. Module complet
On donne pour finir le code complet contenant les fonctions permettant de générer ces arrangements :
| 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | def generer_arrangements(elements, k, arr=()): # fonction permettant de générer la liste des arrangements de k éléments pris dans un ensemble de n éléments # generer_arrangements(['a','b','c'], 2) → ('a','b'), ('a','c'), ('b','a'), ('b','c'), ('c','a'), ('c','b') # si k=0 if k==0: # On renvoie une liste contenant l'arrangement arr. return [arr] else: # sinon # initialisation de la liste des arrangements arrangements = [] # parcours des éléments et de leur indice for i,e in enumerate(elements): # appel récursif pour k-1 : generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,)) # arguments : elements[0:i] + elements[i+1:] → elements, k-1 → k, arr + (e,) → arr arrangements += generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,)) # Renvoie la liste des arrangements. return arrangements def generateur_arrangements(elements, k, arr=()): # fonction permettant de générer tous les arrangements de k éléments pris dans un ensemble de n éléments # generateur_arrangements(['a','b','c'], 2) → ('a','b'), ('a','c'), ('b','a'), ('b','c'), ('c','a'), ('c','b') # si k=0 if k==0: # On génère l'arrangement arr. yield arr else: # sinon # parcours des éléments et de leur indice for i,e in enumerate(elements): # appel récursif pour k-1 : generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,)) : yield from .. # arguments : elements[0:i] + elements[i+1:] → elements, k-1 → k, arr + (e,) → arr yield from generateur_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,)) print("Génération des arrangements de k éléments pris dans un ensemble de n éléments..\n") # valeur de k k = 3 print("k = " + str(k)) # création de la liste d'éléments elements = ['a','b','c','d'] print("E = " + str(elements).replace("[","{").replace("]","}")) print() print("I. Version n°1 : fonction récursive classique\n") # Génère la liste des arrangements de k éléments pris dans un ensemble de n éléments. arrangements = generer_arrangements(elements, k) print("Liste des arrangements :\n") # Affiche la liste des arrangements print(arrangements) print();print() print("II. Version n°2 : fonction génératrice avec yield et yield from\n") # Crée le générateur permettant de parcourir la liste des arrangements de k éléments pris dans un ensemble de n éléments. gen_arrangements = generateur_arrangements(elements, k) print("Liste des arrangements :\n") # parcours des arrangements un à un for arrangement in gen_arrangements: # Affiche l'arrangement. print(arrangement) print();print() print("III. Application : tiercés dans l'ordre\n") # valeur de k k = 3 print("k = " + str(k)) # création de la liste d'éléments : numéros au départ elements = [1, 2, 3, 4] print("E = " + str(elements).replace("[","{").replace("]","}")) print() # Crée le générateur permettant de parcourir la liste des arrangements de k éléments pris dans un ensemble de n éléments gen_arrangements = generateur_arrangements(elements, k) print("Liste des tiercés dans l'ordre possibles :\n") # parcours les arrangements un à un : tiercés possibles for arrangement in gen_arrangements: # Affiche l'arrangement : tiercé possible print(arrangement) |
V. Conclusion
On a donc d'abord montré comment obtenir à l'aide d'un arbre de dénombrement tous les arrangements de 3 éléments pris dans un ensemble à 4 éléments. Puis, on a proposé une première fonction récursive en Python permettant de générer la liste des arrangements de k éléments pris parmi n.
Enfin, on a créé une fonction génératrice à partir de ce code pour éviter les problèmes de mémoire insuffisante.
Sources :
https://fr.wikipedia.org/wiki/Arrangement
https://fr.wikipedia.org/wiki/Combin...9p%C3%A9tition
https://fr.wikipedia.org/wiki/Combinatoire
https://fr.wikipedia.org/wiki/Pseudo-code
https://gayerie.dev/docs/python/pyth...es-generateurs
https://docs.python.org/3/whatsnew/3.3.html#pep-380
http://villemin.gerard.free.fr/Puzzle/HazTierc.htm