Discussion :

[laureat]

Bonjour,

Je cherche une méthode (enfin un algorithme) qui permet de trouver intélligement un ou plusieurs sous ensemble d'un ensemble de n éléments tel que la somme des élements de sous-ensemble égale à zéro.
Voici un exemple:
J'ai un ensemble a : +5, +10, +11, +19, -26, -12, -3, -3, -1
Je connais déjà que la somme des éléments de mon ensemble a est égale à zéro.
Je cherche à déterminer un ou plusieurs sous ensmble de a à condition que la somme de sous ensemble est égale à zéro.

Donc:
Sous ensemble 1: +5, +11, +10, -26.
Sous ensemble 2: +19, -12, -3, , -3, -1

Des idées?
Merci par avance

[kwariz]

Salut,


Quelques questions :

Tu as beaucoup d'entiers à traiter ?
La liste contient-elle des 0 ?
La somme de ta liste de départ est-elle toujours nulle ?
Il te faut toutes les solutions ou juste une ?

Quelques pistes :

Tu as déjà résolu des problèmes de type knapsack ?

[laureat]

Merci pour ta réponse.

Salut,


Quelques questions :

Tu as beaucoup d'entiers à traiter ?
?

oui jusqu'à 1000.

La liste contient-elle des 0 ??

oui.

La somme de ta liste de départ est-elle toujours nulle ???

Il te faut toutes les solutions ou juste une ???

il me faut toutes les solutions sans doublons pour une liste de petite taille et u nombre Q de solutions pour une liste de grande taille.

Quelques pistes :

Tu as déjà résolu des problèmes de type knapsack ?

non
Merci.

[kwariz]

ok, on va essayer de formaliser ça un peu mieux.

Tu as une liste de départ L qui contient l éléments (Li), i de 1 à l, tels que somme(Li)=0.
Tu en tires deux sous listes :
P la liste des Li tels que Li>0, P=(Pi), i de 1 à p
N la liste des -Li tels que Li<0, N=(Ni), i de 1 à n
On aura p+n <= l (puisqu'on enlève les 0 inutiles)
L'idée est simple ensuite, pour toute sous liste P' de P, si tu trouves une sous liste N' de N telle que somme(P')=somme(N') alors L'=P' U -N' est une solution de ton problème. Tu pourras ensuite générer L' U (0) si tu avais des 0 dans la liste L qui est aussi une solution.

Il faut faire attention aux Li en double quand tu génères une sous-liste.

Une autre façon de voir les choses serait par exemple de se dire qu'une sous liste P' de P est P privé de P'', si tu trouves une sous liste N'' telle que somme(P'')=somme(N'') alors N'=N privé de N'' sera telle que somme(N')=somme(P') ... donc deux solutions : -N' U P' et -N'' U P''.

J'y réfléchis un peu plus et je reviens vers toi.

En attendant tu peux essayer de voir un peu la littérature sur le sujet, une petite recherche sur subset sum problem , partition problem, knapsack problem pour te faire une idée de la difficulté de trouver toutes les solutions et des heuristiques mises en oeuvre pour ces problèmes.

C'est un exo de cours ?

[kwariz]

Salut,

plus de nouvelles ?
Sinon je ne trouve pas de méthodes simples et générale pour ton problème. Même en réduisant le nombre de valeurs le problèmes explose rapidement (normal car il est NP complet). Si la densité est élevée (nombre d'occurence par valeur/nombre de valeurs) alors il y a pas mal de solutions, mais parcourir tout l'espace de recherche ...

[souviron34]

on peut déjà diviser le problème :

sachant que la somme doit être égale à zéro, ce sera forcément n nombres positifs + m nombres négatifs.

En divisant / train la table entre positiifs et négatifs, on n'a "plus" qu'à regarder en gros la moitié.

Maintenant, pour toute valeur négative, on a un max sur la valeur positive possible.

si n1 = -26, tout n2 > 26 est à rejeter.

En ayant trié la table par ordre croissant, on peut donc, en prenant chaque point négatif, partir uniquement de ce point positif et descendre ...

Et, si on veut faire complet, on peut inverser le tri et recommencer.

On aura donc toutes les sommes positives correspondant à un nombre négatif et réciproquement.

Il me semble que du coup le calcul est en O(n3), non ?

[kwariz]

Salut souviron34,

je ne comprends vraiment ce que tu proposes, mais comment t'affranchis-tu du parcours éventuel de toutes les sous listes possibles pour les négatifs ou les positifs ?

[souviron34]

une somme peut être nulle seulement à la condition qu'il y ait au moins 1 nombre négatif et un nombre positif, non ??

Si on divise le tableau entre positifs et négatifs en triant par ordre croisssant :

+5, +10, +11, +19, -26, -12, -3, -3, -1

devient

-26 -12 -3 -1 5 10 11 19

On examine les nombres négatifs un par un :

pour -26

on démarre à 19 en positif on cherche 7 au max. . On part du premier (5) et on s'arrête dès que le chiffre vaut plus que 7. Donc c'est le seul possible et ça marche pas.

on passe à 11, on cherche 15. Donc on ne peut aller que jusqu'à 10 (11 est déjà pris).

etc etc.

Pour 5, on cherche 21. Dès qu'on arrive à 11 on a fini : toute combinason supérieure donnerait plus que 26.


Ensute, on continue pour le chiffre négatif suivant.

A la fin, on complète par l'itération symétique.

On ne fait donc pas Cnp, mais un chiffre beaucoup plus petit, et d'autant plus petit en rapport que la dimension est grande.

[kwariz]

OK, tu te limites à ne cherche une solution qu'avec 1 nombre négatif par exemple et non toutes les combinaisons possibles de nombres négatifs ?

[souviron34]

OK, tu te limites à ne cherche une solution qu'avec 1 nombre négatif par exemple et non toutes les combinaisons possibles de nombres négatifs ?

Non, pas du tout. Je limite simplement des possibilités par la contrainte donnée :

On examine les nombres négatifs un par un :
....
A la fin, on complète par l'itération symétique.

On ne fait donc pas Cnp, mais un chiffre beaucoup plus petit, et d'autant plus petit en rapport que la dimension est grande.

En fait, c'est un peu "divide and conquer"

Pour chaque nombre négatif A, pour que la somme soit nulle il faut n nombres positifs de valeur max (-A) et de denière autre valeur (-A) - le premier positif

Ensuite, pour chaque nombre posiitf, réciproquement

[kwariz]

Mais dans le cas (-13,-12,-1,1,11,14) tu ne trouves pas la solution (-13,-12,11,14) ? Tu es quand même obligé de parcourir d'une manière ou d'une autre les combinaisons de chaque côté, non ?

[souviron34]

là j'ai fait pour un chiffre, déjà tu as réduis considérablement.

Tu passes ensuite à 2, mais en appliquant la même technique

Puis 3..

L'important c'est la limite sur le nombre max possible de l'autre signe et la valeur max suivante.

et tu as une limite sur le nombre des chiffres intervenant dans la somme, ainsi que siur la somme des chiffres possible envisageable.. tu peux aussi ajouter ces 2 limites.

Par exemple si tu cherches les combinaisons pour un nombre entre 10 et 20, forcément tu ne pourras avoir qu'un seul nombre >= 10 et <= nombre au max. On peut par exemple penser à se faire un tableau des limites des dzaines.

[kwariz]

Oui mais du coup ça donne une complexité à nouveau exponentielle car tu dois chercher les sommes de toutes les combinaisons de nombres négatifs au moins (1 parmi les n, puis 2 parmi les n, ..., qui donnent des sommes <= somme(negatif)/2) et pour chaque combinaison chercher une somme équivalente sur les combinaisons de nombres positifs.

[souviron34]

Oui mais du coup ça donne une complexité à nouveau exponentielle car tu dois chercher les sommes de toutes les combinaisons de nombres négatifs au moins (1 parmi les n, puis 2 parmi les n, ..., qui donnent des sommes <= somme(negatif)/2) et pour chaque combinaison chercher une somme équivalente sur les combinaisons de nombres positifs.

je ne te suis pas tout à fait, là..

pour n nombres à 1 chiffre, je cherche dans (n/2)-x , x étant le symétique du point cherché.

Donc pour A, on cherche dans (n/2-A) en gros

Maintenant, si on prend des nombres de départ de 2 chiffres, on réduiit quand même pas mal..

Comme j'ai dit, ça doit rester en n3, je pense, mais le nombre d'opérations est considérablement réduit sur de grands tableaux.

et n3 n'est pas !n

[kwariz]

Prenons un exemple, comment ça se passe avec :

(-1,-2, ..., -999,-500000 , 1,2, ...,999,500000)

Si on commence sur les négatifs, on va devoir parcourir toutes les combinaisons faisables avec -1,-2, ..., -999. La dernière combinaisons qui prend donc tous les nombre de -1 à -999 devra chercher un somme équivalente dans les positifs qui ne sera trouvée qu'après avoir parcouru toutes les combinaisons que l'on peut faire avec les nombre de 1 à 999.

Edit: finalement on se donne du mal pour un primopostant qui a disparu mais le problème est sympa