User

[Actualité] Python : générer les partitions d'un ensemble

par

User

, 18/10/2023 à 14h03 (7675 Affichages)

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 :

Nom : nombre_bell.png
Affichages : 8937
Taille : 1,8 Ko

Nom : nombre_bell.png
Affichages : 8937
Taille : 1,8 Ko

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 :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

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

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
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 :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
# 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 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 :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
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:]

La fonction principale devient :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
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 :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
# 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 :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

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
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
 
 
#---------------------------------------------------------------
#--------------------- 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 [elements]
        return # sortie de la fonction
 
    #1er élément de la liste
    element = elements[0]
 
    # 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] + [[element] + 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 [[element]] + 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/pyth...es-generateurs