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