Python : générer l'ensemble des parties d'un ensemble,

Un billet blog de Denis Hulo

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 :

644474

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 :

644475.


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 :

644557



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 :

644473

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 :

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 :

# 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 :

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 :

# 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 :

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 :

# 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 :

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 :

# 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 :

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/Ensemble_des_parties_d%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/tutorial/datastructures.html#sets
https://gayerie.dev/docs/python/python3/iterateur_generateur.html#les-generateurs