Python : générer les partitions d'un ensemble d'éléments,

Un billet blog de Denis Hulo

I. Introduction

Après les parties d'un ensemble, on s'intéresse maintenant aux partitions d'un ensemble :

L'objectif sera donc cette fois de créer une fonction Python qui pourra générer la liste des partitions d'un ensemble d'éléments.

On va également créer une fonction génératrice qui va permettre d'obtenir les partitions sans avoir besoin de les stocker dans une liste.


II. Partitions d'un ensemble


II-A. Définition mathématique

En mathématiques, une partition d'un ensemble E est un ensemble de parties non vides de E deux à deux disjointes et dont l'union est E.

Soit par exemple E un ensemble de 3 éléments :

E = {1, 2, 3}

L'ensemble E a les partitions suivantes :

• {{1}, {2}, {3}} ;
  
• {{1, 3}, {2}} ;
  
• {{1}, {2, 3}} ;
  
• {{1, 2}, {3}} ;
  
• {{1, 2, 3}}.
  

On remarque que :

• {∅, {1, 3}, {2}} n'est pas une partition parce qu'elle contient l'ensemble vide ∅ ou {} ;
  
• {{1, 2}, {2, 3}} n'est pas une partition parce que l'élément 2 appartient à plus d'une partie ;
  
• {{1}, {2}} n'est pas une partition de {1, 2, 3} car l'union de tous les éléments est {1, 2} ; c'est une partition de {1, 2}.
  

Le nombre de partitions d'un ensemble à n éléments en exactement k sous-ensembles est le nombre de Stirling de seconde espèce noté S(n, k).

Le nombre total de partitions de cet ensemble est égal au nombre de Bell :

645315

Ces nombres forment une suite d'entiers dont on peut calculer les premiers termes :

B0 = 1, B1 = 1, B2 = 2,
B3 = 5, B4 = 15, B5 = 52,
B6 = 203, B7 = 877, ...


II-B. Génération des partitions d'un ensemble

Reprenons notre ensemble {1, 2, 3}.

On part de l'ensemble vide E0 = {}.

La partition de l'ensemble vide est la partition vide {}.

Puis, on va chercher à obtenir successivement les listes de partitions des ensembles à 1, 2 et 3 éléments :


1. Partition de l'ensemble E1 = {1} :

• {{1}} : ajout de {1} à l'ensemble vide {}.
  

2. Liste des partitions P2 de l'ensemble E2 = {1, 2} :

• {{1}, {2}} : ajout de {2} à la partition {{1}} ;
  
• {{1, 2}} : ajout de 2 à {1} pour former le sous-ensemble {1, 2}.
  

3. Liste des partitions P3 de l'ensemble E3 = {1, 2, 3}.

On ajoute {3} à la partition {{1}, {2}} et on distribue 3 sur les sous-ensembles de la partition :

• {{1}, {2}, {3}} : ajout de {3} à l'ensemble {{1}, {2}} ;
  
• {{1, 3}, {2}} : ajout de 3 à {1} pour former le sous-ensemble {1, 3} ;
  
• {{1}, {2, 3}} : ajout de 3 à {2} pour former le sous-ensemble {2, 3} ;
  

On ajoute {3} à la partition {{1, 2}} et 3 au sous-ensemble {1, 2} :

• {{1, 2}, {3}} : ajout de {3} à l'ensemble {{1, 2}} ;
  
• {{1, 2, 3}} : ajout de 3 au sous-ensemble {1, 2} pour former le sous-ensemble {1, 2, 3}.
  

Dans le cas général, on distribue donc à chaque étape le nouvel élément en+1 sur les partitions de la liste Pn, et sur leurs sous-ensembles pour former la nouvelle liste de partitions Pn+1.

On peut donc écrire la relation :

Pn+1 = distribuer_element(Pn, en+1)

avec :

P0 = {}


L'objectif est alors de déterminer la fonction distribuer_element qui relie Pn à Pn+1.



III. Implémentation en Python


III-A. Génération de la liste des partitions d'un ensemble

On crée tout d'abord la fonction permettant de passer d'une liste de partitions d'un ensemble à n éléments, à une liste de partitions d'un ensemble à n+1 éléments :

def distribuer_element_v1(partitions, element):
# fonction permettant de distribuer l'élément sur les partitions et leurs sous-ensembles pour former les nouvelles partitions :
# {{e1}, {e2}} -> {{e1}, {e2}, {e3}} ; {{e1, e3}, {e2}} ; {{e1}, {e2, e3}} ; etc.

# initialisation de la nouvelle liste de partitions
parts=[]

# parcours de la liste des partitions passée en argument
for partition in partitions:
# ajout d'une nouvelle partition constituée de la partition d'origine à laquelle on ajoute l'élément : {{e1}, {e2}} -> {{e1}, {e2}, {e3}}
parts += [partition + []]
# parcours des sous-ensembles des partitions (subset)
for i, subset in enumerate(partition):
# ajout d'une partition constituée du sous-ensemble subset auquel on ajoute l'élément : {{e1}, {e2}} -> {{e1, e3}, {e2}}
parts += [partition[:i] + [subset + ] + partition[i+1:]]

# renvoie la liste des partitions résultat de la distribution de l'élément sur les partitions et leurs sous-ensembles
return parts



Enfin, on crée la fonction principale permettant de générer les partitions d'une ensemble donné :

def generer_partitions(elements):
# version n°1 : génère la liste des partitions de l'ensemble de départ représenté par la liste elements

# initialisation de la liste des partitions
partitions = [[]]

# parcours des éléments de la liste passée en argument
for ei in elements:
# génération des partitions de l'ensemble Ei = {e1, e2, ..., ei}
partitions = distribuer_element_v1(partitions, ei)

# renvoie la liste des partitions de l'ensemble de départ représenté par elements
return partitions


Testons maintenant la fonction :

# création de la liste des éléments de l'ensemble de départ E = {1, 2, 3}
elements = [1, 2, 3]

# version n°1 : génère la liste des partitions de l'ensemble représenté par la liste elements
partitions = generer_partitions(elements)

# affiche les partitions une à une
for partition in partitions:
print(format_ensemble(partition))


Le code affiche :

{1, 2, 3}
{{1, 3}, {2}}
{{1}, {2, 3}}
{{1, 2}, {3}}
{{1, 2, 3}}



III-B. Fonction génératrice avec yield

Comme on a pu le constater précédemment, si la taille n de l'ensemble de départ augmente, le nombre de partitions générées (nombre de Bell Bn) 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.

Pour cela, Python dispose du mot-clé yield qui permet de transformer une fonction en générateur :

def distribuer_element_v2(gen_partitions, element):
# fonction génératrice permettant de distribuer l'élément sur les partitions et leurs sous-ensembles pour former les nouvelles partitions :
# {{e1}, {e2}} -> {{e1}, {e2}, {e3}} ; {{e1, e3}, {e2}} ; {{e1}, {e2, e3}} ; etc.

# parcours des partitions une à une
for partition in gen_partitions:
# ajout d'une nouvelle partition constituée de la partition d'origine à laquelle on ajoute l'élément : {{e1}, {e2}} -> {{e1}, {e2}, {e3}}
yield partition + []
# parcours des sous-ensembles des partitions (subset)
for i, subset in enumerate(partition):
# ajout d'une partition constituée du sous-ensemble subset auquel on ajoute l'élément : {{e1}, {e2}} -> {{e1, e3}, {e2}}
yield partition[:i] + [subset + ] + partition[i+1:]



La fonction principale devient :

def generateur_partitions(elements):
# version n°2 : crée un générateur permettant de parcourir les partitions une à une

# initialisation de la variable gen_partitions : [] -> {}
gen_partitions = iter([[]])

# parcours des éléments de la liste passée en argument
for ei in elements:
# création du générateur permettant de parcourir les partitions de l'ensemble Ei = {e1, e2, ..., ei}
gen_partitions = distribuer_element_v2(gen_partitions, ei)

# renvoie le générateur permettant de parcourir les partitions une à une
return gen_partitions


Testons maintenant la fonction :

# création de la liste des éléments de l'ensemble de départ E = {1, 2, 3}}
elements = [1, 2, 3]

# version n°2 : crée le générateur permettant de parcourir la liste des partitions de l'ensemble de départ
gen_partitions = generateur_partitions(elements)

# affiche les partitions une à une
for partition in gen_partitions:
print(format_ensemble(partition))


Le code affiche :

{1, 2, 3}
{{1, 3}, {2}}
{{1}, {2, 3}}
{{1, 2}, {3}}
{{1, 2, 3}}



III-C. Module complet

On donne enfin le code complet du module pour effectuer les tests :

def distribuer_element_v1(partitions, element):
# fonction permettant de distribuer l'élément sur les partitions et leurs sous-ensembles pour former les nouvelles partitions :
# {{e1}, {e2}} -> {{e1}, {e2}, {e3}} ; {{e1, e3}, {e2}} ; {{e1}, {e2, e3}} ; etc.

# initialisation de la nouvelle liste de partitions
parts=[]

# parcours de la liste des partitions passée en argument
for partition in partitions:
# ajout d'une nouvelle partition constituée de la partition d'origine à laquelle on ajoute l'élément : {{e1}, {e2}} -> {{e1}, {e2}, {e3}}
parts += [partition + []]
# parcours des sous-ensembles des partitions (subset)
for i, subset in enumerate(partition):
# ajout d'une partition constituée du sous-ensemble subset auquel on ajoute l'élément : {{e1}, {e2}} -> {{e1, e3}, {e2}}
parts += [partition[:i] + [subset + ] + partition[i+1:]]

# renvoie la liste des partitions résultat de la distribution de l'élément sur les partitions et leurs sous-ensembles
return parts


def generer_partitions(elements):
# version n°1 : génère la liste des partitions de l'ensemble de départ représenté par la liste elements

# initialisation de la liste des partitions
partitions = [[]]

# parcours des éléments de la liste passée en argument
for ei in elements:
# génération des partitions de l'ensemble Ei = {e1, e2, ..., ei}
partitions = distribuer_element_v1(partitions, ei)

# renvoie la liste des partitions de l'ensemble de départ représenté par elements
return partitions


#---------------------------------------------------------------
#------------------- fonction génératrice ----------------------
#---------------------------------------------------------------


def distribuer_element_v2(gen_partitions, element):
# fonction génératrice permettant de distribuer l'élément sur les partitions et leurs sous-ensembles pour former les nouvelles partitions :
# {{e1}, {e2}} -> {{e1}, {e2}, {e3}} ; {{e1, e3}, {e2}} ; {{e1}, {e2, e3}} ; etc.

# parcours des partitions une à une
for partition in gen_partitions:
# ajout d'une nouvelle partition constituée de la partition d'origine à laquelle on ajoute l'élément : {{e1}, {e2}} -> {{e1}, {e2}, {e3}}
yield partition + []
# parcours des sous-ensembles des partitions (subset)
for i, subset in enumerate(partition):
# ajout d'une partition constituée du sous-ensemble subset auquel on ajoute l'élément : {{e1}, {e2}} -> {{e1, e3}, {e2}}
yield partition[:i] + [subset + ] + partition[i+1:]


def generateur_partitions(elements):
# version n°2 : crée un générateur permettant de parcourir les partitions une à une

# initialisation de la variable gen_partitions : [] -> {}
gen_partitions = iter([[]])

# parcours des éléments de la liste passée en argument
for ei in elements:
# création du générateur permettant de parcourir les partitions de l'ensemble Ei = {e1, e2, ..., ei}
gen_partitions = distribuer_element_v2(gen_partitions, ei)

# renvoie le générateur permettant de parcourir les partitions une à une
return gen_partitions


#---------------------------------------------------------------
#--------------------- fonction récursive ----------------------
#---------------------------------------------------------------


def generateur_partitions_recur(elements):
# fonction récursive : crée un générateur permettant de parcourir les partitions une à une
# source : https://stackoverflow.com/questions/65845727/time-complexity-of-finding-all-partitions-of-a-set

# si la liste contient 1 élément
if len(elements) == 1:
yield
return # sortie de la fonction

#1er élément de la liste
element = elements

# parcours des partitions une à une
for partition in generateur_partitions_recur(elements[1:]):

# parcours des sous-ensembles des partitions (subset)
for i, subset in enumerate(partition):
# ajout d'une partition constituée du sous-ensemble subset auquel on ajoute l'élément : {{e1}, {e2}} -> {{e1, e3}, {e2}}
yield partition[:i] + [ + subset] + partition[i+1:]

# ajout d'une nouvelle partition constituée de la partition d'origine à laquelle on ajoute l'élément : {{e1}, {e2}} -> {{e1}, {e2}, {e3}}
yield [] + partition


def format_ensemble(elements):
# convertit une liste d'éléments en une chaîne représentant un emsemble :
# ['a', ['b', 'c']] -> {a, {b, c}}

# remplace les crochets par des accolades
s = str(elements).replace("[","{").replace("]","}")

# supprime les apostrophes
s = s.replace("'","")

# renvoie la chaîne de caractère représentant l'ensemble : {a, {b, c}}
return s


print("Enemble de départ :\n")

# création de la liste des éléments de l'ensemble de départ E = {1, 2, 3}
elements = [1, 2, 3]

# affiche l'ensemble E = {1, 2, 3}
print("E = " + format_ensemble(elements))
print()

print("Génération des partitions de l'ensemble..\n")

print("I. Version n°1 : méthode classique\n")

# version n°1 : génère la liste des partitions de l'ensemble représenté par la liste elements
partitions = generer_partitions(elements)

print("Liste des partitions de l'ensemble :\n")

# affiche les partitions une à une
for partition in partitions:
print(format_ensemble(partition))

print()

print("II. Version n°2 : fonction génératrice avec yield\n")

# version n°2 : crée le générateur permettant de parcourir la liste des partitions de l'ensemble de départ
gen_partitions = generateur_partitions(elements)

print("Liste des partitions de l'ensemble :\n")

# affiche les partitions une à une
for partition in gen_partitions:
print(format_ensemble(partition))


Il contient également la version récursive de la fonction génératrice.



IV. Conclusion

Après avoir montré comment obtenir successivement les partitions d'un ensemble à 1, 2, ..., n éléments, on a donc pu générer en Python la liste des partitions d'un ensemble quelconque.

Enfin, on a créer une fonction génératrice à partir de ce code, pour éviter les problèmes de mémoire insuffisante.


Sources :

https://fr.wikipedia.org/wiki/Partition_d%27un_ensemble
https://fr.wikipedia.org/wiki/Ensemble
https://fr.wikipedia.org/wiki/Nombre_de_Bell
https://fr.wikipedia.org/wiki/Nombre_de_Stirling
https://gayerie.dev/docs/python/python3/iterateur_generateur.html#les-generateurs