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

Un billet blog de Denis Hulo

[SIZE=3]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 :



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

B₀ = 1, B₁ = 1, B₂ = 2,
B₃ = 5, B₄ = 15, B₅ = 52,
B₆ = 203, B₇ = 877, ...

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

Reprenons notre ensemble {1, 2, 3}.

On part de l'ensemble vide E₀ = {}.

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 E₁ = {1} :

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

2. Liste des partitions P₂ de l'ensemble E₂ = {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 P₃ de l'ensemble E₃ = {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 e_n+1 sur les partitions de la liste P_n, et sur leurs sous-ensembles pour former la nouvelle liste de partitions P_n+1.

On peut donc écrire la relation :

P_n+1 = distribuer_element(P_n, e_n+1)

avec :

P₀ = {}

L'objectif est alors de déterminer la fonction distribuer_element qui relie P_n à P_n+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 :



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


Testons maintenant la fonction :


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 B_n) 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 :



La fonction principale devient :


Testons maintenant la fonction :


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 :

[CODE=Python]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 + [[element]]]
# 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 + [element]] + 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 + [[element]]
# 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 + [element]] + 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

#---------------------------------------------------------------
#---------------------[/]]...