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

Un billet blog de Denis Hulo

[SIZE=3]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 2³ parties dans E :

card(𝑃(E)) = 2^card(E) = 2³ = 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 2ⁿ 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 {e₁,e₂} = {e₂,e₁}, ce qui n'est pas le cas pour des tuples (e₁,e₂) ≠ (e₂,e₁). Cependant, dans le produit cartésien {(), e₁}∗{(), e₂}∗...∗{(), e_n}, 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 2ⁿ parties d'un ensemble à n éléments de 0 à 2ⁿ-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 :



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 :


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 :


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 :


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 :


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 :


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 :


Testons maintenant la fonction :


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 (2ⁿ) 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]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[/ei + (ej,)]...