Mathématiques et Python : initiation au problème de la somme de sous-ensembles (subset sum problem)

Un billet blog de Denis Hulo

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 23 parties dans E :

card(𝑃(E)) = 2card(E) = 23 = 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 2n 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 2n parties d'un ensemble à n éléments de 0 à 2n-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 :

650479

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 :

651150

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 :

651151

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

651152

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 :

650610

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 :

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 :

# 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 :

650443

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 :

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 :

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 :

# 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 :

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 :

# 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 (2n) 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 :

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 :

# 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 :

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 :

# 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 :

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%C3%A8me_de_la_somme_de_sous-ensembles
https://fr.wikipedia.org/wiki/Probl%C3%A8me_NP-complet
https://fr.wikipedia.org/wiki/Ensemble_des_parties_d%27un_ensemble
https://fr.wikipedia.org/wiki/Programmation_dynamique
https://gayerie.dev/docs/python/python3/iterateur_generateur.html
https://fr.wikipedia.org/wiki/Lettrage_comptable
https://www.developpez.net/forums/d2100724/general-developpement/algorithme-mathematiques/algorithmes-structures-donnees/sous-ensemble-valeurs-dont-somme-nulle