[Actualité] Analyse combinatoire et Python : les combinaisons avec répétition
par
, 03/04/2024 à 15h27 (5155 Affichages)
I. Introduction
Après les combinaisons sans répétition, on s'intéresse maintenant aux combinaisons avec répétition :
L'objectif sera cette fois de créer une fonction en Python qui pourra générer la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments.
On va ensuite montrer comment transformer ce code en une fonction génératrice qui va nous permettre d'obtenir les combinaisons sans avoir besoin de les stocker dans une liste.
II. Combinaisons avec répétition
D'après Wikipedia, en analyse combinatoire, une combinaison avec répétition est une combinaison où donc l'ordre des éléments n'importe pas et où, contrairement à une combinaison classique (sans répétition), chaque élément de la combinaison peut apparaître plusieurs fois.
Par exemple, lorsque dix dés à six faces (numérotées de 1 à 6) sont jetés, le résultat fourni par ces dix dés, si l'ordre dans lequel sont jetés les dés n'est pas pris en compte, (par exemple un 2, trois 4, deux 5 et quatre 6, sans retenir à quel dé précisément correspond chaque face) est une combinaison des différentes faces apparaissant sur chaque dé, et où chaque face peut apparaître plusieurs fois.
Cette expérience peut être modélisée par une loi multinomiale dans laquelle chaque combinaison possible est associée à un coefficient multinomial.
Dans un jeu de dominos, les 28 pièces représentent les combinaisons avec répétition de 2 éléments pris dans un ensemble E = {blanc, 1, 2, 3, 4 ,5, 6} à 7 éléments.
Le nombre de combinaisons avec répétition de k éléments pris dans un ensemble à n éléments est égal au nombre de k-combinaisons (sans répétition) de n + k – 1 éléments :
On peut remarquer avec cette formule que le nombre de combinaisons croit rapidement quand k et n augmentent.
III. Génération des combinaisons avec répétition
Prenons par exemple un ensemble de n=3 éléments :
E = {a, b, c}
On souhaite obtenir la liste des combinaisons de k=4 éléments pris avec remise dans l'ensemble E, c'est-à-dire générer la liste des 4-combinaisons avec répétition :
(a, a, a, a), (a, a, a, b), ..., (c, c, c, c).
On va d'abord associer à chaque élément de cet ensemble un indice débutant à 0 comme en Python :
(a, b, c) → (0, 1, 2)
On génère ensuite les 4-uplets ou quadruplets d'indices (i0, i1, i2, i3) (croissants au sens large) et leur combinaison, du premier (0, 0, 0, 0) au dernier (2, 2, 2, 2), dans cet ordre :
(0, 0, 0, 0) → (a, a, a, a)
(0, 0, 0, 1) → (a, a, a, b)
(0, 0, 0, 2) → (a, a, a, c)
(0, 0, 1, 1) → (a, a, b, b)
(0, 0, 1, 2) → (a, a, b, c)
(0, 0, 2, 2) → (a, a, c, c)
(0, 1, 1, 1) → (a, b, b, b)
(0, 1, 1, 2) → (a, b, b, c)
(0, 1, 2, 2) → (a, b, c, c)
(0, 2, 2, 2) → (a, c, c, c)
(1, 1, 1, 1) → (b, b, b, b)
(1, 1, 1, 2) → (b, b, b, c)
(1, 1, 2, 2) → (b, b, c, c)
(1, 2, 2, 2) → (b, c, c, c)
(2, 2, 2, 2) → (c, c, c, c)
On incrémente donc à chaque fois les indices des k-uplets (i0, i1, i2, i3) en commençant par la droite, un peu comme pour les chiffres des nombres entiers, mais de façon à toujours conserver un ordre croissant des indices i0 ≤ i1 ≤ i2 ≤ i3 ≤ 2.
Dans le même temps, on transforme chaque k-uplet d'indices croissants en une k-combinaison d'éléments de E en utilisant la correspondance entre indices et éléments de E : (0, 1, 2) → (a, b, c).
IV. Implémentation en Python
IV-A. Génération des combinaisons avec répétition
On présente maintenant une fonction qui génère la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments :
Code Python : 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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 def generer_combinaisons(elements, k): # fonction permettant de générer la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments # generer_combinaisons(['a','b','c'], 2) → ('a','a'), ('a','b'), ('a','c'), ('b','b'), ('b','c'), ('c','c') # nombre d'éléments de l'ensemble n = len(elements) # initialisation de la liste d'indices correspondant à une k-combinaison : [0, 0, .., 0] → ('a', 'a', .., 'a') indices = [0] * k # On crée la 1re combinaison à partir de la liste d'indices. ex. : [0, 0, 0] → ('a', 'a', 'a') k_combinaison = tuple(elements[i] for i in indices) # initialisation de la liste avec la 1re combinaison k_combinaisons = [k_combinaison] # tant que vrai while True: # parcours des indices de la liste for i in reversed(range(k)): # Si la valeur de l'indice est différente de n-1. if indices[i] != n - 1: break # On sort de la boucle : indice trouvé else: # sinon break # On sort de la boucle. # copie (k-i) fois la valeur (indices[i] + 1) à partir de l'indice i dans la liste indices[i:] = [indices[i] + 1] * (k - i) # On génère la combinaison correspondant à la liste d'indices. k_combinaison = tuple(elements[i] for i in indices) # ajout de la combinaison à la liste k_combinaisons.append(k_combinaison) # renvoi la liste des combinaisons return k_combinaisons
Le code est basé sur la fonction combinations_with_replacement présentée dans la documentation du module itertools.
Testons maintenant la fonction :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11 # valeur de k k = 4 # création de la liste d'éléments elements = ['a','b','c'] # Génère la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments. combinaisons = generer_combinaisons(elements, k) # Affiche la liste des combinaisons. print(combinaisons)
Le code affiche :
[('a', 'a', 'a', 'a'), ('a', 'a', 'a', 'b'), ('a', 'a', 'a', 'c'), ('a', 'a', 'b', 'b'), ('a', 'a', 'b', 'c'), ('a', 'a', 'c', 'c'), ('a', 'b', 'b', 'b'), ('a', 'b', 'b', 'c'), ('a', 'b', 'c', 'c'), ('a', 'c', 'c', 'c'), ('b', 'b', 'b', 'b'), ('b', 'b', 'b', 'c'), ('b', 'b', 'c', 'c'), ('b', 'c', 'c', 'c'), ('c', 'c', 'c', 'c')]
IV-B. Fonction génératrice avec yield
Comme on l'a vu précédemment, le nombre de combinaisons 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 de l'instruction yield qui permet de transformer la fonction précédente en générateur :
Code Python : 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
20
21
22
23
24
25
26
27
28 def generateur_combinaisons(elements, k): # fonction permettant de générer la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments # generateur_combinaisons(['a','b','c'], 2) → ('a','a'), ('a','b'), ('a','c'), ('b','b'), ('b','c'), ('c','c') # nombre d'éléments de l'ensemble n = len(elements) # initialisation de la liste d'indices correspondant à une k-combinaison : [0, 0, .., 0] → ('a', 'a', .., 'a') indices = [0] * k # On génère la 1re combinaison. ex. : [0, 0, 0] → ('a', 'a', 'a') yield tuple(elements[i] for i in indices) while True: # parcours des indices de la liste indices for i in reversed(range(k)): # Si la valeur de l'indice est différente de n-1 if indices[i] != n - 1: break # On sort de la boucle : indice trouvé else: return # copie (k-i) fois la valeur (indices[i] + 1) à partir de l'indice i dans la liste indices[i:] = [indices[i] + 1] * (k - i) # On génère la combinaison correspondant aux indices. yield tuple(elements[i] for i in indices)
Vous pouvez retrouver cette fonction dans la documentation du module itertools.
Testons la maintenant :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14 # valeur de k k = 4 # création de la liste d'éléments elements = ['a','b','c'] # Crée le générateur permettant de parcourir la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments. gen_combinaisons = generateur_combinaisons(elements, k) print("Liste des combinaisons avec répétitions :\n") # Affiche les combinaisons une à une. for combinaison in gen_combinaisons: print(combinaison)
Le code affiche :
Liste des combinaisons avec répétition :
('a', 'a', 'a', 'a')
('a', 'a', 'a', 'b')
('a', 'a', 'a', 'c')
('a', 'a', 'b', 'b')
('a', 'a', 'b', 'c')
('a', 'a', 'c', 'c')
('a', 'b', 'b', 'b')
('a', 'b', 'b', 'c')
('a', 'b', 'c', 'c')
('a', 'c', 'c', 'c')
('b', 'b', 'b', 'b')
('b', 'b', 'b', 'c')
('b', 'b', 'c', 'c')
('b', 'c', 'c', 'c')
('c', 'c', 'c', 'c')
IV-C. Application : génération des triplets (x, y, z) tels que x + y + z = 4
Déterminer les triplets (x, y, z) de ℕ3 tels que x + y + z = 4.
On peut se dire que l'on a trois types d'objets : ceux du type X, ceux du type Y et ceux du type Z. On doit en choisir 4 avec remise dans l'ensemble E = {X, Y, Z}. Le nombre x sera donné par le nombre d'éléments du type X choisis, y par le nombre d'éléments du type Y et z par ceux du type Z :
Code Python : 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 # valeur de k k = 4 # création de la liste d'éléments elements = ['X', 'Y', 'Z'] # Crée le générateur permettant de parcourir la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments. gen_combinaisons = generateur_combinaisons(elements, k) print("Liste des combinaisons et leur triplet (x, y, z) tel que x + y + z = 4 :\n") # Affiche les triplets (x, y, z) tels que x + y + z = 4. for combinaison in gen_combinaisons: # détermination du nombre de 'X', de 'Y' et de 'Z' pour chaque combinaison x, y, z = combinaison.count("X"), combinaison.count("Y"), combinaison.count("Z") # Affiche la combinaison et son triplet (x, y, z). print(str(combinaison) + " → " + str((x, y, z)))
Le code affiche :
Liste des combinaisons et leur triplet (x, y, z) tel que x + y + z = 4 :
('X', 'X', 'X', 'X') → (4, 0, 0)
('X', 'X', 'X', 'Y') → (3, 1, 0)
('X', 'X', 'X', 'Z') → (3, 0, 1)
('X', 'X', 'Y', 'Y') → (2, 2, 0)
('X', 'X', 'Y', 'Z') → (2, 1, 1)
('X', 'X', 'Z', 'Z') → (2, 0, 2)
('X', 'Y', 'Y', 'Y') → (1, 3, 0)
('X', 'Y', 'Y', 'Z') → (1, 2, 1)
('X', 'Y', 'Z', 'Z') → (1, 1, 2)
('X', 'Z', 'Z', 'Z') → (1, 0, 3)
('Y', 'Y', 'Y', 'Y') → (0, 4, 0)
('Y', 'Y', 'Y', 'Z') → (0, 3, 1)
('Y', 'Y', 'Z', 'Z') → (0, 2, 2)
('Y', 'Z', 'Z', 'Z') → (0, 1, 3)
('Z', 'Z', 'Z', 'Z') → (0, 0, 4)
IV-D. Module complet
On donne pour finir le code complet contenant les fonctions permettant de générer ces combinaisons :
Code Python : 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
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135 def generer_combinaisons(elements, k): # fonction permettant de générer la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments # generer_combinaisons(['a','b','c'], 2) → ('a','a'), ('a','b'), ('a','c'), ('b','b'), ('b','c'), ('c','c') # nombre d'éléments de l'ensemble n = len(elements) # initialisation de la liste d'indices correspondant à une k-combinaison : [0, 0, .., 0] → ('a', 'a', .., 'a') indices = [0] * k # On crée la 1re combinaison à partir de la liste d'indices. ex. : [0, 0, 0] → ('a', 'a', 'a') k_combinaison = tuple(elements[i] for i in indices) # initialisation de la liste avec la 1re combinaison k_combinaisons = [k_combinaison] # tant que vrai while True: # parcours des indices de la liste for i in reversed(range(k)): # Si la valeur de l'indice est différente de n-1. if indices[i] != n - 1: break # On sort de la boucle : indice trouvé else: # sinon break # On sort de la boucle. # copie (k-i) fois la valeur (indices[i] + 1) à partir de l'indice i dans la liste indices[i:] = [indices[i] + 1] * (k - i) # On génère la combinaison correspondant à la liste d'indices. k_combinaison = tuple(elements[i] for i in indices) # ajout de la combinaison à la liste k_combinaisons.append(k_combinaison) # renvoi la liste des combinaisons return k_combinaisons def generateur_combinaisons(elements, k): # fonction permettant de générer la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments # generateur_combinaisons(['a','b','c'], 2) → ('a','a'), ('a','b'), ('a','c'), ('b','b'), ('b','c'), ('c','c') # nombre d'éléments de l'ensemble n = len(elements) # initialisation de la liste d'indices correspondant à une k-combinaison : [0, 0, .., 0] → ('a', 'a', .., 'a') indices = [0] * k # On génère la 1re combinaison. ex. : [0, 0, 0] → ('a', 'a', 'a') yield tuple(elements[i] for i in indices) while True: # parcours des indices de la liste indices for i in reversed(range(k)): # Si la valeur de l'indice est différente de n-1 if indices[i] != n - 1: break # On sort de la boucle : indice trouvé else: return # copie (k-i) fois la valeur (indices[i] + 1) à partir de l'indice i dans la liste indices[i:] = [indices[i] + 1] * (k - i) # On génère la combinaison correspondant aux indices. yield tuple(elements[i] for i in indices) print("Génération des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments..\n") # valeur de k k = 4 print("k = " + str(k)) # création de la liste d'éléments elements = ['a','b','c'] print("E = " + str(elements).replace("[","{").replace("]","}")) print() print("I. Version n°1 : méthode classique\n") # Génère la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments. combinaisons = generer_combinaisons(elements, k) print("Liste des combinaisons avec répétition :\n") # Affiche la liste des combinaisons print(combinaisons) print();print() print("II. Version n°2 : fonction génératrice avec yield\n") # Crée le générateur permettant de parcourir la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments. gen_combinaisons = generateur_combinaisons(elements, k) print("Liste des combinaisons avec répétition :\n") # Affiche les combinaisons une à une. for combinaison in gen_combinaisons: print(combinaison) print();print() print("III. Application : génération des triplets (x, y, z) tels que x + y + z = 4\n") # valeur de k k = 4 print("k = " + str(k)) # création de la liste d'éléments elements = ['X', 'Y', 'Z'] print("E = " + str(elements).replace("[","{").replace("]","}")) print() # Crée le générateur permettant de parcourir la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments gen_combinaisons = generateur_combinaisons(elements, k) print("Liste des combinaisons et leur triplet (x, y, z) tel que x + y + z = 4 :\n") # Affiche les triplets (x, y, z) tels que x + y + z = 4 for combinaison in gen_combinaisons: # détermination du nombre de 'X', de 'Y' et de 'Z' pour chaque combinaison x, y, z = combinaison.count("X"), combinaison.count("Y"), combinaison.count("Z") # Affiche la combinaison et son triplet (x, y, z). print(str(combinaison) + " → " + str((x, y, z)))
V. Conclusion
Après avoir décrit brièvement l'algorithme permettant d'obtenir la liste des combinaisons avec répétition, on a pu proposer une première fonction en Python basée sur cet algorithme.
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/Combin...9p%C3%A9tition
https://fr.wikipedia.org/wiki/Combin...9p%C3%A9tition
https://fr.wikipedia.org/wiki/Combinatoire
https://docs.python.org/fr/3/library/itertools.html
https://gayerie.dev/docs/python/pyth...es-generateurs
https://www.mathraining.be/chapters/35?type=1&which=118