User

I. Introduction

D'après Wikipedia, le problème de la somme de sous-ensembles (en anglais : subset sum problem) est un problème de décision important en complexité algorithmique et en cryptologie.

Il peut être décrit de la manière suivante : étant donné un ensemble E de n entiers, existe-t-il un sous-ensemble de E dont la somme des éléments est nulle ?

Par exemple, pour l'ensemble {-8, -3, -2, 4, 5}, la réponse est oui car la somme des éléments du sous-ensemble {-3, -2, 5} est nulle, par contre pour {-6, -1, 2, 3, 8} la réponse est non.

Ce problème est NP-complet, c'est-à-dire considéré comme difficile à résoudre efficacement par un algorithme.

On souhaite dans notre cas montrer comment générer l'ensemble des parties de l'ensemble E en économisant la mémoire, puis implémenter cette méthode en Python pour rechercher les combinaisons dont la somme est nulle.

Dans le même esprit, on va également créer une fonction génératrice qui va permettre d'obtenir les sous-ensembles sans avoir besoin de les stocker dans une liste.



II. Génération des sous-ensembles

II-A. Définition : Ensemble des parties d'un ensemble

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.


II-B. Génération des sous-ensembles : méthode naïve avec les codes binaires

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 :



La colonne Nombre d'ajouts correspondant au nombre total d'ajouts d'éléments nécessaires pour composer le sous-ensemble.

On remarque que pour créer chacune des parties de l'ensemble de départ, on a besoin d'ajouter à chaque fois tous les éléments qui composent ces sous-ensembles.


II-C. Génération des sous-ensembles à l'aide du produit cartésien

Comme on a pu le montrer dans un précédent billet, on peut générer les parties d'un ensemble à l'aide du produit cartésien de deux ensembles.

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


On peut modéliser ce problème à l'aide d'un arbre binaire sur lequel on génère les sous-ensembles de E :



On remarque cette fois que pour créer chacune des parties de l'ensemble de départ, on a juste besoin d'ajouter le nouvel élément au sous-ensemble du niveau supérieur en descendant à droite dans l'arbre.

Il s'agit d'un principe utilisé en programmation dynamique.



III. Problème de la somme de sous-ensembles

Prenons maintenant l'ensemble de départ E = {-5, 1, 2, 3} dans lequel on souhaite rechercher un sous-ensemble dont la somme des nombres entiers soit nulle.

On peut à nouveau modéliser ce problème à l'aide d'un arbre binaire sur lequel on génère les sous-ensembles de E :



On peut maintenant compter le nombre d'ajouts nécessaires avant d'obtenir une combinaison d'entiers dont la somme est nulle :



On a donc besoin de réaliser seulement 13 ajouts avant de trouver la bonne combinaison, et 15 sont nécessaires pour générer la totalité des sous-ensembles.

Alors que dans la version avec les code binaires, on aurait eu besoin de 20 ajouts pour identifier la première somme nulle et 32 au total :



Il existe bien sûr d'autres moyens pour optimiser l'algorithme, mais notre objectif sera donc avant tout de chercher à économiser la mémoire.


IV. 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. C'est pourquoi, par commodité, on ajoutera les éléments à une liste plutôt qu'à un Set.


IV-A. Génération des sous-ensembles à partir de leur code binaire

On présente maintenant la fonction qui génère les parties d'un ensemble de nombres entiers à partir de leur code binaire et retient celles à somme nulle :

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
def subset_sum_v1(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 = []
    resultats = []
 
    # 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)
 
        if partie!=() and sum(partie)==0:
            resultats.append(partie)
 
 
    # renvoi la liste des parties et les sous-ensembles à somme nulle
    return (parties, resultats)

Testons maintenant la fonction :

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
# création de l'ensemble E = {-5, 1, 2, 3}
E = Ensemble([-5, 1, 2, 3])
 
print("E = " + str(E)+ "\n")
 
# génère l'ensemble des parties de E dans P
P = E.subset_sum()
 
# affiche les parties
print("P(E) = " + str(P))
 
print()
 
# affiche les sous-ensembles dont la somme est nulle
print("Sommes nulles = " + str(P.resultats)+ "\n")

Le code affiche :

P(E) = {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {-5}, {-5, 3}, {-5, 2}, {-5, 2, 3}, {-5, 1}, {-5, 1, 3}, {-5, 1, 2}, {-5, 1, 2, 3}}

Sommes nulles = [(-5, 2, 3)]



IV-B. Génération des sous-ensembles à l'aide du produit cartésien

Pour représenter ces ensembles en Python et pouvoir réaliser des opérations entre eux, il nous faut utiliser notre classe classe Ensemble :



On va en plus initialiser la liste des résultats du problème de subset sum au moment de la création de l'objet :

Code Python :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
class Ensemble:
 
    def __init__(self, elements, contient_parties=False, resultats=[]):
        # 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
 
        # on initialise l'attribut résultats
        self.resultats = resultats

IV-B-1. Surcharge de l'opérateur « * »

Nous devons également modifier légèrement la méthode __mul__() de notre classe :

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
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
        E = Ensemble([], self.resultats[:])
 
        # 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
                    subset = ei + ej # création du sous-ensemble
                else: # sinon, si le tuple ej contient plus de 1 élément
                    subset = ei + (ej,) # création du sous-ensemble
 
                # si le sous-ensemble contient des entiers dont la somme est nulle
                if ej!=() and sum(subset)==0:
                    E.resultats.append(subset)
 
                # ajout du couple d'éléments à la liste. Exemple : E.elements = E.elements + [(ei,ej)]  
                E.elements.append(subset)
 
        # renvoie l'ensemble produit des 2 autres ensembles passés en argument
        return E

Cette méthode permet donc d'obtenir le produit de 2 ensembles :

E1 * E2 = {1, 2} * {3, 4} = {(1, 3), (1, 4), (2, 3), (2, 4)}

On a juste besoin de vérifier en plus si la somme des entiers du sous-ensemble obtenu est nulle pour l'ajouter ou pas aux résultats.

Testons maintenant l'opérateur « * » portant sur 2 objets de la classe Ensemble :

Code Python :

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

1
2
3
4
5
6
7
8
9
10
# création du 1er objet Ensemble : E1 = {1, 2}
E1 = Ensemble([1,2]) 
 
# création du 2e objet Ensemble : E2 = {3, 4}
E1 = Ensemble([3,4])  
 
E = E1 * E2 # produit des 2 ensembles : E = E1 × E2
 
# affiche le résultat
print("E = " + str(E))

Le code affiche :

E = {(1, 3), (1, 4), (2, 3), (2, 4)}


IV-B-2. Méthode permettant de générer les sous-ensembles

Nous allons finalement ajouter une méthode subset_sum à la classe :

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
class Ensemble:
    ....
    def subset_sum(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 = {()}
 
        elements = sorted(self.elements)
 
        # on effectue le produit P = {(), e1}*{(), e2}* ... *{(), en}
        for ei in elements:
            Ei = Ensemble([(),ei]) # création de l'ensemble {(), ei}
            P = P*Ei # équivalent à : P = P*{(), ei}
 
        # renvoie l'ensemble des parties de self
        return P

Elle permet donc de générer les combinaisons de nombres entiers en retenant celles dont la somme est nulle.

On ajoute maintenant ces lignes pour tester la méthode :

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
# création de l'ensemble E = {-5, 1, 2, 3}
E = Ensemble([-5, 1, 2, 3])
 
print("E = " + str(E)+ "\n")
 
# génère l'ensemble des parties de E dans P
P = E.subset_sum()
 
# affiche les parties de E
print("P(E) = " + str(P))
 
print()
 
# affiche les sous-ensembles dont la somme est nulle
print("Sommes nulles = " + str(P.resultats)+ "\n")

Le code affiche :

P(E) = {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {-5}, {-5, 3}, {-5, 2}, {-5, 2, 3}, {-5, 1}, {-5, 1, 3}, {-5, 1, 2}, {-5, 1, 2, 3}}

Sommes nulles = [(-5, 2, 3)]



IV-C. Fonction génératrice des sous-ensembles 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 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 le sous-ensemble suivant 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 créer une fonction génératrice.

On peut maintenant écrire la fonction permettant de générer les sous-ensembles après ajout du nouvel élément :

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
def gen_subsets(sous_ensembles, element):
    # fonction permettant de générer les nouveaux sous-ensembles après ajout de l'élément
 
    # parcours des sous-ensembles (subset)
    for subset in sous_ensembles:
 
        # ordre de renvoyer le sous-ensemble : descente à gauche dans l'arbre binaire
        yield subset
 
        # création du nouveau sous-ensemble avec ajout du nouvel élément
        new_subset = tuple(subset) + (element,)
 
        # ordre de renvoyer le nouveau sous-ensemble  : descente à droite dans l'arbre binaire
        yield new_subset

Comme les éléments de l'ensemble de départ sont triés, on peut également choisir de ne générer le nouveau sous-ensemble (new_subset) que si la somme de ses entiers est inférieure ou égale à zéro :

Code Python :

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

1
2
3
        # on génère le nouveau sous-ensemble que si la somme de ses entiers est inférieure ou égale à zéro
        if sum(new_subset)<=0:
            yield new_subset

Enfin, on crée la fonction principale permettant de générer les sous-ensembles :

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
def generateur_subsets(elements):
    # permet de génèrer les sous-ensembles à partir de l'ensemble de départ
 
    # tri des éléments de l'ensemble de départ
    elements.sort()
 
    # initialisation de la variable sous_ensembles avec un élément vide : {{}}
    sous_ensembles = iter([()])
 
    # parcours des éléments de la liste de départ
    for ei in elements:
        # on génère les nouveaux sous-ensembles après ajout de ei
        sous_ensembles = gen_subsets(sous_ensembles, ei)
 
    # renvoie la générateur permettant de parcourir les sous-ensembles obtenus
    return sous_ensembles

Testons maintenant notre fonction afin de rechercher les sous-ensembles à sommes nulles :

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
# création de l'ensemble E = {-5, 1, 2, 3}
E = [-5, 1, 2, 3]
 
print("E = " + str(E)+ "\n")
 
# création du  générateur des sous-ensembles de E
gen_subsets = generateur_subsets(E)
 
# parcours des sous-ensembles
for subset in gen_subsets:
 
    # si la somme des entiers du sous-ensemble subset est nulle
    if subset!=() and sum(subset)==0:
        # afffiche le sous-ensemble d'entiers
        print("Somme nulle : " + str(subset))

Le code affiche :

E = [-5, 1, 2, 3]

Somme nulle : (-5, 2, 3)


Cette fonction génératrice est d'ailleurs disponible dans le module présenté par la suite.


IV-D. 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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
class Ensemble:
 
    def __init__(self, elements, contient_parties=False, resultats=[]):
        # 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
 
        # on initialise l'attribut résultats
        self.resultats = resultats
 
 
    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
        E = Ensemble([], self.resultats[:])
 
        # 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
                    subset = ei + ej # création du sous-ensemble
                else: # sinon, si le tuple ej contient plus de 1 élément
                    subset = ei + (ej,) # création du sous-ensemble
 
                # si le sous-ensemble contient des entiers dont la somme est nulle
                if ej!=() and sum(subset)==0:
                    E.resultats.append(subset)
 
                # ajout du couple d'éléments à la liste. Exemple : E.elements = E.elements + [(ei,ej)]  
                E.elements.append(subset)
 
        # renvoie l'ensemble produit des 2 autres ensembles passés en argument
        return E
 
 
    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 subset_sum(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 = {()}
 
        elements = self.elements
 
        # on effectue le produit P = {(), e1}*{(), e2}* ... *{(), en}
        for ei in elements:
            Ei = Ensemble([(),ei]) # création de l'ensemble {(), ei}
            P = P*Ei # équivalent à : P = P*{(), ei}
 
        # 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 subset_sum_v1(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 = []
    resultats = []
 
    # 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)
 
        if partie!=() and sum(partie)==0:
            resultats.append(partie)
 
 
    # renvoi la liste des parties et les sous-ensembles à somme nulle
    return (parties, resultats)
 
 
def gen_subsets(sous_ensembles, element):
    # fonction permettant de générer les nouveaux sous-ensembles après ajout de l'élément
 
    # parcours des sous-ensembles (subset)
    for subset in sous_ensembles:
 
        # ordre de renvoyer le sous-ensemble : descente à gauche dans l'arbre binaire
        yield subset
 
        # création du nouveau sous-ensemble avec ajout du nouvel élément
        new_subset = tuple(subset) + (element,)
 
        # on génère le nouveau sous-ensemble que si la somme de ses entiers est inférieure ou égale à zéro :
        if sum(new_subset)<=0:
            yield new_subset
 
 
def generateur_subsets(elements):
    # permet de génèrer les sous-ensembles à partir de l'ensemble de départ
 
    # tri des éléments de l'ensemble de départ
    elements.sort()
 
    # initialisation de la variable sous_ensembles avec un élément vide : {{}}
    sous_ensembles = iter([()])
 
    # parcours des éléments de la liste de départ
    for ei in elements:
        # on génère les nouveaux sous-ensembles après ajout de ei
        sous_ensembles = gen_subsets(sous_ensembles, ei)
 
    # renvoie la générateur permettant de parcourir les sous-ensembles obtenus
    return sous_ensembles
 
 
print("I. Somme de sous-ensembles : méthode avec les codes binaires \n")
 
E = Ensemble([-5, 1, 2, 3])
 
print("E = " + str(E)+ "\n")
 
# génère l'ensemble des parties de E
parties, resultats = subset_sum_v1(E.elements)
 
# création de l'ensemble à partir de la liste des parties
P = Ensemble(parties, contient_parties=True)
 
# affiche la liste des sous-ensembles de E
print("P(E) = " + str(P))
 
print()
 
# affiche les sous-ensembles dont la somme des entiers est nulle
print("Sommes nulles = " + str(resultats)+ "\n")
 
 
print("=======================================================================\n")
 
 
print("II. Somme de sous-ensembles : produit cartésien et arbre binaire\n")
 
# création de l'ensemble E = {-5, 1, 2, 3}
E = Ensemble([-5, 1, 2, 3])
 
print("E = " + str(E)+ "\n")
 
# génère l'ensemble des parties de E dans P et les sous-ensembles dont la somme des entiers est nulle
P = E.subset_sum()
 
# affiche les parties
print("P(E) = " + str(P))
 
print()
 
# affiche les sous-ensembles dont la somme des entiers est nulle
print("Sommes nulles = " + str(P.resultats)+ "\n")
 
 
print("=======================================================================\n")
 
 
print("III. Somme de sous-ensembles : fonction génératrice et arbre binaire\n")
 
# création de l'ensemble E = {-5, 1, 2, 3}
E = Ensemble([-5, 1, 2, 3])
 
print("E = " + str(E)+ "\n")
 
# création du générateur des sous-ensembles de E
gen_subsets = generateur_subsets(E.elements)
 
# parcours des sous-ensembles
for subset in gen_subsets:
    # si la somme des entiers du sous-ensemble subset est nulle
    if subset!=() and sum(subset)==0:
        # afffiche le sous-ensemble d'entiers
        print("Somme nulle : " + str(subset))
        # break

V. Conclusion

Comme on a pu le constater, la génération des sous-ensembles sur un arbre binaire permet de conserver les éléments précédents, et donc de limiter le nombre total d'ajouts dans les sous-ensembles.

Ces algorithmes ont toutefois un temps d'exécution exponentiel en fonction de la taille de l'ensemble de départ, et sont donc exploitables en pratique uniquement pour des ensembles de dimension modeste.

Il existe bien sûr des algorithmes plus efficaces, utilisant notamment la programmation dynamique, mais comme on l'a déjà dit, ce type de problème est de toute façon considéré comme difficile à résoudre efficacement.


Sources :

https://fr.wikipedia.org/wiki/Probl%...sous-ensembles
https://fr.wikipedia.org/wiki/Probl%C3%A8me_NP-complet
https://fr.wikipedia.org/wiki/Ensemb...%27un_ensemble
https://fr.wikipedia.org/wiki/Programmation_dynamique
https://gayerie.dev/docs/python/pyth...enerateur.html
https://fr.wikipedia.org/wiki/Lettrage_comptable
https://www.developpez.net/forums/d2...nt-somme-nulle