I. IntroductionOn 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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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
Vous avez lu gratuitement 0 articles depuis plus d'un an.
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer � vous proposer des publications.
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer � vous proposer des publications.