[Actualité] Python : générer l'ensemble des parties d'un ensemble
par
, 03/10/2023 à 13h05 (9458 Affichages)
I. Introduction
On souhaite d'abord montrer comment générer en Python l'ensemble des parties d'un ensemble, un peu comme on développerait un produit de facteurs :
Pour représenter ces ensembles en Python et pouvoir réaliser des opérations entre eux, on va créer une classe dans laquelle on redéfinira l'opérateur « * ». Puis, on ajoutera une méthode à cette classe permettant de générer la totalité des parties d'un ensemble donné.
Enfin, pour compléter le billet, on expliquera comment obtenir le même résultat à partir cette fois des codes binaires représentant les sous-ensembles recherchés.
II. Ensemble des parties d'un ensemble
II-A. Définition mathématique
En mathématiques, l'ensemble des parties d'un ensemble, parfois appelé ensemble puissance, est l'ensemble de tous les sous-ensembles d'un ensemble donné (y compris cet ensemble lui-même et l'ensemble vide).
Soit par exemple E un ensemble de 3 éléments :
E = {a, b, c}
L'ensemble des parties de cet ensemble donne :
𝑃(E) = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}
Il y a donc 23 parties dans E :
card(𝑃(E)) = 2card(E) = 23 = 8
où card(E) représente la cardinalité ou le nombre d'éléments de l'ensemble E.
Plus généralement, pour un ensemble à n éléments on a donc 2n parties.
On retrouve cette formule quand on souhaite calculer la somme des coefficients binomiaux.
En effet, ces coefficients donnent le nombre de parties à k éléments d'un ensemble à n éléments (k étant compris entre 0 et n), et ils sont notés :
Par conséquent, d'après la formule du binôme, la somme des coefficients de 0 à n est égale au nombre total de parties d'un ensemble à n éléments :
.
II-B. Génération des parties d'un ensemble à l'aide du produit cartésien
Reprenons notre ensemble E à 3 éléments :
E = {a, b, c}
Soit maintenant le produit cartésien des 3 sous-ensembles :
𝑃 = {(), a}∗{(), b}∗{(), c}
Qui donne après regroupement des sous-ensembles de même taille :
𝑃 = {(), a, b, c, (a,b), (a,c), (b,c), (a,b,c)}
On reconnaît là l'ensemble des parties de l'ensemble E que l'on peut réécrire plus proprement :
𝑃(E) = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}
Un peu comme si on souhaitait développer le produit de facteurs :
𝑃 = (1+a)(1+b)(1+c)
𝑃 = (1 + a + b + ab)(1+c) = 1 + a + b + ab + c + ac + bc + abc
𝑃 = 1 + a + b + c + ab + ac + bc + abc
A noter que pour des ensembles ou des sous-ensembles l'ordre n'a pas d'importance {e1,e2} = {e2,e1}, ce qui n'est pas le cas pour des tuples (e1,e2) ≠ (e2,e1). Cependant, dans le produit cartésien {(), e1}∗{(), e2}∗...∗{(), en}, on a pas deux tuples contenant les mêmes éléments permutés, par conséquent on peut le voir comme un ensemble de parties avec la même cardinalité.
II-C. Génération des parties en utilisant les codes binaires représentant les sous-ensembles recherchés
On numérote d'abord les 2n parties d'un ensemble à n éléments de 0 à 2n-1, puis on évalue le code binaire de chacun de ces numéros. Enfin, on applique la règle suivante pour obtenir le sous-ensemble à partir du code binaire :
- bit à 0 : on ignore l'élément à la même position dans l'ensemble de départ ;
- bit à 1 : on retient l'élément à cette position dans l'ensemble de départ.
Si on part à nouveau de notre ensemble à 3 éléments :
E = {a, b, c}
On obtient ainsi la liste numérotée des parties de cet ensemble :
III. Implémentation en Python
Un ensemble ou Set forme un type de données Python. Il s'agit d'une collection non ordonnée sans élément en double.
Toutefois, on souhaite dans notre cas pouvoir conserver l'ordre d'ajout des éléments et pouvoir éventuellement les trier et les regrouper pour l'affichage de l'ensemble des parties. C'est pourquoi, par commodité, on ajoutera les éléments à une liste plutôt qu'à un Set.
III-A. Classe Ensemble et produit cartésien
Pour représenter ces ensembles en Python et pouvoir réaliser des opérations entre eux, il nous faut créer une classe Ensemble :
Notre classe comportera en plus une méthode particulière __init__() appelé constructeur et dont le code est exécuté quand la classe est instanciée.
Elle va nous permettre de définir la liste des éléments de l'ensemble au moment de la création de l'objet :
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 class Ensemble: def __init__(self, elements, contient_parties=False): # méthode constructeur de la classe # on définit la liste des éléments uniques de l'ensemble en conservant l'ordre. Exemple : ["a", "b", "b", "c"] -> ["a", "b", "c"] -> {a, b, c} self.elements = [ei for i,ei in enumerate(elements) if ei not in elements[:i]] # on indique s'il s'agit de parties d'un ensemble self.contient_parties = contient_parties def __str__(self): # permet d'afficher l'ensemble des éléments ou des parties : # E = {(a,c), (a,d), (b,c), (b,d)} # E = {{}, {a}, {b}, {a,b}} # suppression des apostrophes (') et copie dans une chaîne : [('a','c'), ('a','d'), ('b','c'), ('b','d')] -> [(a,c), (a,d), (b,c), (b,d)] s = str(self.elements).replace("'","") # remplacement des crochets par des accolades pour représenter l'ensemble : [(a,c), (a,d), (b,c), (b,d)] -> {(a,c), (a,d), (b,c), (b,d)} s = s.replace("[","{").replace("]","}") s = s.replace(",)",")") if self.contient_parties: # si l'ensemble contient des parties # remplacement des parenthèses par des accolades : {(), (a), (b), (a,b)} -> {{}, {a}, {b}, {a,b}} s = s.replace("(","{").replace(")","}") # retourne la chaîne de caractères représentant l'ensemble des éléments ou des parties return s
La méthode __str__() permet d'afficher suivant la valeur de l'attribut contient_parties, un ensemble d'éléments sous la forme :
{(), a, b, (a, b)}
Ou un ensemble de parties sous la forme :
{{}, {a}, {b}, {a, b}}
Pour tester ces méthodes, nous ajoutons simplement quelques lignes au module :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 # création de l'objet Ensemble : E = {a, b} E = Ensemble(['a','b']) # affiche le contenu de l'ensemble print("E = " + str(E))
Le code affiche :
E = {a, b}
III-A-1. Surcharge de l'opérateur « * »
Pour surcharger l'opérateur « * » et l'appliquer à 2 objets Ensemble, nous devons également ajouter une méthode __mul__() à notre classe :
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 class Ensemble: .... def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 ensembles d'éléments : E1 * E2 = {a, b} * {c, d} = {(a,c), (a,d), (b,c), (b,d)} # initialisation de la liste d'éléments elements=[] # parcours de la liste d'éléments de self for ei in self.elements: if not isinstance(ei, tuple): ei=(ei,) # si ei n'est pas un tuple on en crée un. # parcours de la liste d'éléments de other for ej in other.elements: if not isinstance(ej, tuple): ej=(ej,) # si ej n'est pas un tuple on en crée un. if len(ej)<=1: # si le tuple ej contient 0 ou 1 élément elements = elements + [ei + ej] # ajout du couple d'éléments à la liste. Exemple : elements = elements + [(ei,ej)] else: # sinon, si le tuple ej contient plus de 1 élément elements = elements + [ei + (ej,)] # ajout du couple d'éléments à la liste # renvoie l'ensemble produit des 2 autres ensembles passés en argument return Ensemble(elements)
Cette méthode permet donc d'obtenir le produit de 2 ensembles :
E1 * E2 = {a, b} * {c, d} = {(a, c), (a, d), (b, c), (b, d)}
Testons maintenant l'opérateur « * » portant sur 2 objets de la classe Ensemble :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 # création du 1er objet Ensemble : E1 = {a, b} E1 = Ensemble(['a','b']) # création du 2e objet Ensemble : E2 = {c, d} E1 = Ensemble(['c','d']) E = E1 * E2 # produit des 2 ensembles : E = E1 × E2 # affiche le résultat print("E = " + str(E))
Le code affiche :
E = {(a, c), (a, d), (b, c), (b, d)}
III-A-2. Méthode permettant de générer l'ensemble des parties d'un ensemble
Nous allons finalement ajouter une méthode generer_parties à la classe :
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 class Ensemble: .... def generer_parties(self): # méthode permettant de générer l'ensemble des parties de self P = Ensemble([()]) # on part d'un ensemble contenant un tuple vide : P = {()} # on effectue le produit P = {(), e1}*{(), e2}* ... *{(), en} for ei in self.elements: Ei = Ensemble([(),ei]) # création de l'ensemble {(), ei} P = P*Ei # équivalent à : P = P*{(), ei} # facultatif : regroupement des tuples de même longueur pour l'affichage des parties P.elements = grouper(P.elements) # on indique qu'il s'agit des parties d'un ensemble P.contient_parties = True # renvoie l'ensemble des parties de self return P
Elle permet donc de générer l'ensemble des parties d'un ensemble donné en utilisant le produit cartésien.
Si on prend par exemple l'ensemble E = {a, b, c}, on obtient le produit cartésien des 3 ensembles :
{(), a}∗{(), b}∗{(), c} = {(), a, b, c, (a,b), (a,c), (b,c), (a,b,c)}
On reconnait alors l'ensemble des parties de l'ensemble E que l'on peut réécrire plus proprement :
𝑃(E) = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}
On ajoute maintenant ces lignes pour tester la méthode :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8 # création de l'ensemble E = {a,b,c} E = Ensemble(['a','b','c']) # génère l'ensemble des parties de E dans P P = E.generer_parties() # affiche le résultat print("P(E) = " + str(P))
Le code affiche :
P(E) = {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}
III-B. Génération des parties d'un ensemble à partir de leur code binaire
On présente pour finir une fonction qui génère les parties d'un ensemble à partir de leur code binaire :
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 generer_parties(elements): # fonction permettant de générer l'ensemble des parties de la liste d'éléments # nombre d'éléments de l'ensemble nombre_elements=len(elements) # nombre total de parties de l'ensemble : 2^card(E) nombre_parties=2**nombre_elements # initialisation de la liste des parties parties = [] # parcours des numéros ou indices des parties : 0 -> nombre_parties-1 for indice_partie in range(nombre_parties): # conversion du numéro ou de l'indice en code binaire : 1 -> 001 code_binaire = "{0:0{1}b}".format(indice_partie, nombre_elements) # création du sous-ensemble à partir du code binaire et de l'ensemble de départ : 001 et {a,b,c} -> {c} partie = tuple([element for element, bit in zip(elements, code_binaire) if bit=='1']) # ajout de la partie à la liste parties.append(partie) # facultatif : regroupement des tuples de même longueur pour l'affichage des parties parties = grouper(parties) # renvoi la liste des parties return parties
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 # création de l'ensemble E = {a,b,c} E = Ensemble(['a','b','c']) # génère l'ensemble des parties de E parties = generer_parties(E.elements) # création de l'ensemble à partir de la liste générée P = Ensemble(parties, contient_parties=True) # affiche le résultat print("P(E) = " + str(P))
Le code affiche :
P(E) = {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}
On note toutefois que si la taille n de l'ensemble de départ augmente, le nombre de parties générées (2n) peut très vite devenir important, ce qui risque d'entrainer des problèmes de mémoire insuffisante (MemoryError). Pour éviter ces débordements, on peut 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 en mémoire dans une liste ou une autre structure de données.
III-C. Module complet
On donne enfin le code complet du module pour effectuer les tests :
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203 def grouper(elements): # regroupement des tuples de même longueur pour l'affichage des parties d'un ensemble : # [(), ("a",), ("a", "b"), ("b",)] -> [(), ("a",), ("b",), ("a", "b")] # {{}, {a}, {a,b}, {b}} -> {{}, {a}, {b}, {a,b}} # initialisation de la liste des éléments liste_elements=[] # tri des éléments elements.sort() # détermination du nombre d'éléments de l'ensemble n=len(elements) # parcours des tailles des sous-ensembles ou parties : 0 -> n for i in range(n+1): # création de la liste des sous-ensembles de taille i Ei = [ei for ei in elements if len(ei)==i] # ajout à la liste liste_elements = liste_elements + Ei # renvoie la liste des éléments (sous-ensembles) regroupés pat taille return liste_elements class Ensemble: def __init__(self, elements, contient_parties=False): # méthode constructeur de la classe # on définit la liste des éléments uniques de l'ensemble en conservant l'ordre. Exemple : ["a", "b", "b", "c"] -> ["a", "b", "c"] -> {a, b, c} self.elements = [ei for i,ei in enumerate(elements) if ei not in elements[:i]] # on indique s'il s'agit de parties d'un ensemble self.contient_parties = contient_parties def __str__(self): # permet d'afficher l'ensemble des éléments ou des parties : # E = {(a,c), (a,d), (b,c), (b,d)} # E = {{}, {a}, {b}, {a,b}} # suppression des apostrophes (') et copie dans une chaîne : [('a','c'), ('a','d'), ('b','c'), ('b','d')] -> [(a,c), (a,d), (b,c), (b,d)] s = str(self.elements).replace("'","") # remplacement des crochets par des accolades pour représenter l'ensemble : [(a,c), (a,d), (b,c), (b,d)] -> {(a,c), (a,d), (b,c), (b,d)} s = s.replace("[","{").replace("]","}") s = s.replace(",)",")") if self.contient_parties: # si l'ensemble contient des parties # remplacement des parenthèses par des accolades : {(), (a), (b), (a,b)} -> {{}, {a}, {b}, {a,b}} s = s.replace("(","{").replace(")","}") # retourne la chaîne de caractères représentant l'ensemble des éléments ou des parties return s def __or__(self, other): # méthode permettant de redéfinir l'opérateur d'union « | » pour 2 ensembles : E1 | E2 = {a, b} + {c, d} = {a, b, c, d} # concaténation des deux listes d'éléments elements = self.elements + other.elements # renvoie l'ensenble résultat de la réunion des 2 autres ensembles passés en argument return Ensemble(elements) def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 ensembles d'éléments : E1 * E2 = {a, b} * {c, d} = {(a,c), (a,d), (b,c), (b,d)} # initialisation de la liste d'éléments elements=[] # parcours de la liste d'éléments de self for ei in self.elements: if not isinstance(ei, tuple): ei=(ei,) # si ei n'est pas un tuple on en crée un. # parcours de la liste d'éléments de other for ej in other.elements: if not isinstance(ej, tuple): ej=(ej,) # si ej n'est pas un tuple on en crée un. if len(ej)<=1: # si le tuple ej contient 0 ou 1 élément elements = elements + [ei + ej] # ajout du couple d'éléments à la liste. Exemple : elements = elements + [(ei,ej)] else: # sinon, si le tuple ej contient plus de 1 élément elements = elements + [ei + (ej,)] # ajout du couple d'éléments à la liste # renvoie l'ensemble produit des 2 autres ensembles passés en argument return Ensemble(elements) def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n E = Ensemble([()]) # on part d'un ensemble contenant un tuple vide : E = {()} # on multiplie n fois E par self à l'aide de l'opérateur * for i in range(n): E = E*self # équivalent à : E = E.__mul__(self) # renvoie l'ensemble résultat de l'opération (self ** n) return E def generer_parties(self): # méthode permettant de générer l'ensemble des parties de self P = Ensemble([()]) # on part d'un ensemble contenant un tuple vide : P = {()} # on effectue le produit P = {(), e1}*{(), e2}* ... *{(), en} for ei in self.elements: Ei = Ensemble([(),ei]) # création de l'ensemble {(), ei} P = P*Ei # équivalent à : P = P*{(), ei} # facultatif : regroupement des tuples de même longueur pour l'affichage des parties P.elements = grouper(P.elements) # on indique qu'il s'agit des parties d'un ensemble P.contient_parties = True # renvoie l'ensemble des parties de self return P def __eq__(self, other): # méthode permettant de redéfinir l'opérateur « == » pour 2 ensembles # renvoie True si les 2 ensembles d'éléments sont égaux return (sorted(self.elements)==sorted(other.elements)) def generer_parties(elements): # fonction permettant de générer l'ensemble des parties de la liste d'éléments # nombre d'éléments de l'ensemble nombre_elements=len(elements) # nombre total de parties de l'ensemble : 2^card(E) nombre_parties=2**nombre_elements # initialisation de la liste des parties parties = [] # parcours des numéros ou indices des parties : 0 -> nombre_parties-1 for indice_partie in range(nombre_parties): # conversion du numéro ou de l'indice en code binaire : 1 -> 001 code_binaire = "{0:0{1}b}".format(indice_partie, nombre_elements) # création du sous-ensemble à partir du code binaire et de l'ensemble de départ : 001 et {a,b,c} -> {c} partie = tuple([element for element, bit in zip(elements, code_binaire) if bit=='1']) # ajout de la partie à la liste parties.append(partie) # facultatif : regroupement des tuples de même longueur pour l'affichage des parties parties = grouper(parties) # renvoi la liste des parties return parties print("I. Produit cartésien :\n") # création du 1er objet Ensemble : E1 = {a, b} E1 = Ensemble(['a','b']) print("E1 = " + str(E1)+ "\n") # création du 2e objet Ensemble : E2 = {c, d} E2 = Ensemble(['c','d']) print("E2 = " + str(E2)+ "\n") E = E1 * E2 # produit des 2 ensembles : E = E1 × E2 print("E = E1 × E2 :\n") # affiche le résultat print("E = " + str(E)+ "\n") print("=======================================================================\n") print("II. Ensemble des parties d'un ensemble :\n") # création de l'ensemble E = {a,b,c} E = Ensemble(['a','b','c']) print("E = " + str(E)+ "\n") print("Version n°1 - Génération des parties à l'aide du produit cartésien :\n") # génère l'ensemble des parties de E dans P P = E.generer_parties() # affiche le résultat print("P(E) = " + str(P)+ "\n") print("Version n°2 - Génération des parties en utilisant les codes binaires :\n") # génère l'ensemble des parties de E parties = generer_parties(E.elements) # création de l'ensemble à partir de la liste générée P = Ensemble(parties, contient_parties=True) # affiche le résultat print("P(E) = " + str(P))
IV. Conclusion
Comme on a pu le constater, la génération de l'ensemble des parties d'un ensemble en Python ne pose pas vraiment de difficulté.
Libre à chacun ensuite de créer une fonction génératrice à partir du code proposé, pour éviter, comme on l'a noté, les problèmes de mémoire insuffisante.
Sources :
https://fr.wikipedia.org/wiki/Ensemb...%27un_ensemble
https://fr.wikipedia.org/wiki/Ensemble
https://fr.wikipedia.org/wiki/Produit_cart%C3%A9sien
https://fr.wikipedia.org/wiki/Coefficient_binomial
https://docs.python.org/fr/3/tutoria...ures.html#sets
https://gayerie.dev/docs/python/pyth...es-generateurs