Quelles sont les combinaisons possibles pour que la somme de nombres donne 59 (par exemple)
=> 9 + 50 (rangs 5 et 6) => 1 + 3 + 55 (1 et 8 et 10) => 1 + 55 + 3 (1 et 10 et 13) ...
Comment procédurè-je alors ? Le but est d'afficher clairement les combinaisons bien sûr.
Cela doit être un problème ultra-classique. Je suis à peu près sûr que tu aurais déjà eu des réponses (avec des références de bouquins par exemple) si tu avais posé ta question là où elle est en charte, à savoir <news:fr.comp.algorithmes>.
J'y redirige la suite de la discussion.
Je suis en train de plancher sur un problème d'algorithme :
Quelles sont les combinaisons possibles pour que la somme de nombres
donne 59 (par exemple)
=> 9 + 50 (rangs 5 et 6)
=> 1 + 3 + 55 (1 et 8 et 10)
=> 1 + 55 + 3 (1 et 10 et 13)
...
Comment procédurè-je alors ? Le but est d'afficher clairement les
combinaisons bien sûr.
Cela doit être un problème ultra-classique. Je suis à peu près sûr que
tu aurais déjà eu des réponses (avec des références de bouquins par
exemple) si tu avais posé ta question là où elle est en charte, à savoir
<news:fr.comp.algorithmes>.
Quelles sont les combinaisons possibles pour que la somme de nombres donne 59 (par exemple)
=> 9 + 50 (rangs 5 et 6) => 1 + 3 + 55 (1 et 8 et 10) => 1 + 55 + 3 (1 et 10 et 13) ...
Comment procédurè-je alors ? Le but est d'afficher clairement les combinaisons bien sûr.
Cela doit être un problème ultra-classique. Je suis à peu près sûr que tu aurais déjà eu des réponses (avec des références de bouquins par exemple) si tu avais posé ta question là où elle est en charte, à savoir <news:fr.comp.algorithmes>.
J'y redirige la suite de la discussion.
loiseauthierry
Michel Olagnon wrote:
Joe Cool wrote:
En fait, tu pourrais aussi préciser que le problème est NP-complet au sens faible, c'est-à-dire qu'il devient vraiment polynomial si on considère les données et non plus leur taille (ou si on code les nombre en unaire, ce qui revient au même), alors que le problème du posteur original était lui exponentiel (mais enfin, tout le monde l'a oublié, lui).
Le problème du posteur original est SubsetSum, sauf que lui il voulait générer toutes les solutions. SubsetSum est pseudo-polynomial, la belle affaire...
Je n'ai pas compris ca comme ca. Le probleme du posteur original est une instance particuliere de SubsetSum, ou : - soit il n'est pas stupide de vouloir lister toutes les solutions(*), et donc le fait que la resolution par programmation dynamique est pseudo-polynomiale donne un algorithme parfaitement satisfaisant si S est petit, ou alors c'est N qui est suffisamment petit pour qu'on puisse faire une recherche exhaustive. - soit le posteur original est inconscient du nombre commun de solutions a lister, et il convient de l'en informer.
Souvenons nous que le posteur original etait dans fr.comp.lang.javascript. On peut douter qu'il veuille resoudre un probleme de cryptographie avancee.
(*) Il est aise de voir qu'il y a 2^N sous-ensembles possibles, et seulement S (= somme de tous les elements positifs - somme de tous les elements negatifs) valeurs possibles pour leurs sommes. On est donc sur qu'il y a des valeurs pour lesquelles il y a plus de 2^N/S solutions. avec N0, S > 1000 par exemple, ca fait deja 1 million de solutions a lister. Avec N0, Sr000, ca fait dans les 10^40.
Michel Olagnon <molagnon@ifremer-a-oter.fr> wrote:
Joe Cool wrote:
En fait, tu pourrais aussi préciser que le problème est NP-complet au
sens faible, c'est-à-dire qu'il devient vraiment polynomial si on
considère les données et non plus leur taille (ou si on code les nombre
en unaire, ce qui revient au même), alors que le problème du posteur
original était lui exponentiel (mais enfin, tout le monde l'a oublié,
lui).
Le problème du posteur original est SubsetSum, sauf que lui il voulait
générer toutes les solutions. SubsetSum est pseudo-polynomial, la belle
affaire...
Je n'ai pas compris ca comme ca.
Le probleme du posteur original est une instance particuliere de SubsetSum,
ou :
- soit il n'est pas stupide de vouloir lister toutes les solutions(*), et
donc le fait que la resolution par programmation dynamique est
pseudo-polynomiale donne un algorithme parfaitement satisfaisant si S est
petit, ou alors c'est N qui est suffisamment petit pour qu'on puisse faire
une recherche exhaustive.
- soit le posteur original est inconscient du nombre commun de solutions
a lister, et il convient de l'en informer.
Souvenons nous que le posteur original etait dans fr.comp.lang.javascript.
On peut douter qu'il veuille resoudre un probleme de cryptographie avancee.
(*) Il est aise de voir qu'il y a 2^N sous-ensembles possibles, et seulement
S (= somme de tous les elements positifs - somme de tous les elements
negatifs) valeurs possibles pour leurs sommes. On est donc sur qu'il y a
des valeurs pour lesquelles il y a plus de 2^N/S solutions. avec N0, S > 1000 par exemple, ca fait deja 1 million de solutions a lister. Avec
N0, Sr000,
ca fait dans les 10^40.
En fait, tu pourrais aussi préciser que le problème est NP-complet au sens faible, c'est-à-dire qu'il devient vraiment polynomial si on considère les données et non plus leur taille (ou si on code les nombre en unaire, ce qui revient au même), alors que le problème du posteur original était lui exponentiel (mais enfin, tout le monde l'a oublié, lui).
Le problème du posteur original est SubsetSum, sauf que lui il voulait générer toutes les solutions. SubsetSum est pseudo-polynomial, la belle affaire...
Je n'ai pas compris ca comme ca. Le probleme du posteur original est une instance particuliere de SubsetSum, ou : - soit il n'est pas stupide de vouloir lister toutes les solutions(*), et donc le fait que la resolution par programmation dynamique est pseudo-polynomiale donne un algorithme parfaitement satisfaisant si S est petit, ou alors c'est N qui est suffisamment petit pour qu'on puisse faire une recherche exhaustive. - soit le posteur original est inconscient du nombre commun de solutions a lister, et il convient de l'en informer.
Souvenons nous que le posteur original etait dans fr.comp.lang.javascript. On peut douter qu'il veuille resoudre un probleme de cryptographie avancee.
(*) Il est aise de voir qu'il y a 2^N sous-ensembles possibles, et seulement S (= somme de tous les elements positifs - somme de tous les elements negatifs) valeurs possibles pour leurs sommes. On est donc sur qu'il y a des valeurs pour lesquelles il y a plus de 2^N/S solutions. avec N0, S > 1000 par exemple, ca fait deja 1 million de solutions a lister. Avec N0, Sr000, ca fait dans les 10^40.
En fait, tu pourrais aussi préciser que le problème est NP-complet au sens faible, c'est-à-dire qu'il devient vraiment polynomial si on considère les données et non plus leur taille (ou si on code les nombre en unaire, ce qui revient au même), alors que le problème du posteur original était lui exponentiel (mais enfin, tout le monde l'a oublié, lui).
Le problème du posteur original est SubsetSum, sauf que lui il voulait générer toutes les solutions. SubsetSum est pseudo-polynomial, la belle affaire... Je n'ai pas compris ca comme ca.
Le probleme du posteur original est une instance particuliere de SubsetSum, ou : - soit il n'est pas stupide de vouloir lister toutes les solutions(*), et donc le fait que la resolution par programmation dynamique est pseudo-polynomiale donne un algorithme parfaitement satisfaisant si S est petit, ou alors c'est N qui est suffisamment petit pour qu'on puisse faire une recherche exhaustive. - soit le posteur original est inconscient du nombre commun de solutions a lister, et il convient de l'en informer.
Souvenons nous que le posteur original etait dans fr.comp.lang.javascript. On peut douter qu'il veuille resoudre un probleme de cryptographie avancee.
(*) Il est aise de voir qu'il y a 2^N sous-ensembles possibles, et seulement S (= somme de tous les elements positifs - somme de tous les elements negatifs) valeurs possibles pour leurs sommes. On est donc sur qu'il y a des valeurs pour lesquelles il y a plus de 2^N/S solutions. avec N0, S >> 1000 par exemple, ca fait deja 1 million de solutions a lister. Avec N0, Sr000, ca fait dans les 10^40.
Et sur le group fclj, on en pense quoi ?
On va pas se mesurer avec des informathématiciens !
Avec l'exemple fourni sur fca, 150 valeurs, il existe un sacré paquet de solutions (j'ai abandonné à 40000 solutions au bout de quelques minutes, avec Opera pour la rapidité du JS, et sans être sûr que mon script ne faisait pas du gruyère dans les solutions...). Alors avec 500 éléments de départ...
Pour des petits ensembles de valeur on peut trouver des algorithmes suffisamment rapides mais reste à comprendre l'intérêt de la manip. Quel est le problème amenant à chercher de façon exhaustive ces combinaisons tellement nombreuses que, à supposer qu'on arrive à les trouver toutes, elles sont inexploitables ?
-- Y.D.
Michel Olagnon <molagnon@ifremer-a-oter.fr> wrote:
Joe Cool wrote:
En fait, tu pourrais aussi préciser que le problème est NP-complet au
sens faible, c'est-à-dire qu'il devient vraiment polynomial si on
considère les données et non plus leur taille (ou si on code les nombre
en unaire, ce qui revient au même), alors que le problème du posteur
original était lui exponentiel (mais enfin, tout le monde l'a oublié,
lui).
Le problème du posteur original est SubsetSum, sauf que lui il voulait
générer toutes les solutions. SubsetSum est pseudo-polynomial, la belle
affaire...
Je n'ai pas compris ca comme ca.
Le probleme du posteur original est une instance particuliere de SubsetSum,
ou :
- soit il n'est pas stupide de vouloir lister toutes les solutions(*), et
donc le fait que la resolution par programmation dynamique est
pseudo-polynomiale donne un algorithme parfaitement satisfaisant si S est
petit, ou alors c'est N qui est suffisamment petit pour qu'on puisse faire
une recherche exhaustive.
- soit le posteur original est inconscient du nombre commun de solutions
a lister, et il convient de l'en informer.
Souvenons nous que le posteur original etait dans fr.comp.lang.javascript.
On peut douter qu'il veuille resoudre un probleme de cryptographie avancee.
(*) Il est aise de voir qu'il y a 2^N sous-ensembles possibles, et seulement
S (= somme de tous les elements positifs - somme de tous les elements
negatifs) valeurs possibles pour leurs sommes. On est donc sur qu'il y a
des valeurs pour lesquelles il y a plus de 2^N/S solutions. avec N0, S >> 1000 par exemple, ca fait deja 1 million de solutions a lister. Avec
N0, Sr000,
ca fait dans les 10^40.
Et sur le group fclj, on en pense quoi ?
On va pas se mesurer avec des informathématiciens !
Avec l'exemple fourni sur fca, 150 valeurs, il existe un sacré paquet
de solutions (j'ai abandonné à 40000 solutions au bout de quelques
minutes, avec Opera pour la rapidité du JS, et sans être sûr que mon
script ne faisait pas du gruyère dans les solutions...). Alors avec
500 éléments de départ...
Pour des petits ensembles de valeur on peut trouver des algorithmes
suffisamment rapides mais reste à comprendre l'intérêt de la manip.
Quel est le problème amenant à chercher de façon exhaustive ces
combinaisons tellement nombreuses que, à supposer qu'on arrive à les
trouver toutes, elles sont inexploitables ?
En fait, tu pourrais aussi préciser que le problème est NP-complet au sens faible, c'est-à-dire qu'il devient vraiment polynomial si on considère les données et non plus leur taille (ou si on code les nombre en unaire, ce qui revient au même), alors que le problème du posteur original était lui exponentiel (mais enfin, tout le monde l'a oublié, lui).
Le problème du posteur original est SubsetSum, sauf que lui il voulait générer toutes les solutions. SubsetSum est pseudo-polynomial, la belle affaire... Je n'ai pas compris ca comme ca.
Le probleme du posteur original est une instance particuliere de SubsetSum, ou : - soit il n'est pas stupide de vouloir lister toutes les solutions(*), et donc le fait que la resolution par programmation dynamique est pseudo-polynomiale donne un algorithme parfaitement satisfaisant si S est petit, ou alors c'est N qui est suffisamment petit pour qu'on puisse faire une recherche exhaustive. - soit le posteur original est inconscient du nombre commun de solutions a lister, et il convient de l'en informer.
Souvenons nous que le posteur original etait dans fr.comp.lang.javascript. On peut douter qu'il veuille resoudre un probleme de cryptographie avancee.
(*) Il est aise de voir qu'il y a 2^N sous-ensembles possibles, et seulement S (= somme de tous les elements positifs - somme de tous les elements negatifs) valeurs possibles pour leurs sommes. On est donc sur qu'il y a des valeurs pour lesquelles il y a plus de 2^N/S solutions. avec N0, S >> 1000 par exemple, ca fait deja 1 million de solutions a lister. Avec N0, Sr000, ca fait dans les 10^40.
Et sur le group fclj, on en pense quoi ?
On va pas se mesurer avec des informathématiciens !
Avec l'exemple fourni sur fca, 150 valeurs, il existe un sacré paquet de solutions (j'ai abandonné à 40000 solutions au bout de quelques minutes, avec Opera pour la rapidité du JS, et sans être sûr que mon script ne faisait pas du gruyère dans les solutions...). Alors avec 500 éléments de départ...
Pour des petits ensembles de valeur on peut trouver des algorithmes suffisamment rapides mais reste à comprendre l'intérêt de la manip. Quel est le problème amenant à chercher de façon exhaustive ces combinaisons tellement nombreuses que, à supposer qu'on arrive à les trouver toutes, elles sont inexploitables ?
