I. Introduction
Aprè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 :
653274
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 :
653275
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 :
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 (indice débutant à 0 : comme en Python)
new_elements = elements[0:i] + elements[i+1:]
# nouveau tuple avec elements en plus
new_arr = arr + elements
# appel récursif pour k-1
arrangements(new_elements, k-1, new_arr)
Fin pour
Fin si
Fin Algo
On va maintenant se baser sur cet algorithme pour écrire nos fonctions en Python.
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 :
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
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 :
# 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 :
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 :
# 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 :
# 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 :
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
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/Combinaison_sans_r%C3%A9p%C3%A9tition
https://fr.wikipedia.org/wiki/Combinatoire
https://fr.wikipedia.org/wiki/Pseudo-code
https://gayerie.dev/docs/python/python3/iterateur_generateur.html#les-generateurs
https://docs.python.org/3/whatsnew/3.3.html#pep-380
http://villemin.gerard.free.fr/Puzzle/HazTierc.htm
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer à vous proposer des publications.