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