Une série de valeurs pour obtenir une valeur X

**Geno312** · 29/09/2007, 21h42

Bonjour à tous !

Je cherche une façon d'obtenir le nombre de combinaisons possibles ayant une série de valeurs (le nombre de valeurs données ainsi que leurs valeurs peuvent varier bien entendu en fonction des paramètres que je donne au départ) pour obtenir une valeur X.

Par exemple,
Supposons que j'ai les chiffres 2,5,10,13 (en ordre croissant) et que je veux obtenir la valeur x=10. J'aurais 3 combinaisons possibles soit 2,2,2,2,2 - 5,5 - 10 ou encore pour obtenir x=30 j'aurais 14 combinaisons possibles.

J'essaie de trouver une solution en programmation dynamique afin d'éviter de tester des combinaisons qui l'on déjà été mais ce n'est pas vraiment évident...

Des idées?

**AnozerOne** · 29/09/2007, 21h51

et tu veux juste récupérer le nombre de combinaisons possibles ou les combinaisons aussi ?

**Geno312** · 29/09/2007, 21h51

Juste le nombre.

**Geno312** · 29/09/2007, 22h02

En gros comment cette partie là fonctionne c'est que j'entre le nombre de valeurs possibles qui est de 4 par exemple. Ensuite, j'indique les différentes valeurs en ordre croissante (Ex: 2, 5, 10, 13). Puis j'indique le nombre de valeurs à trouver le nombre de combinaisons (Ex: 2) ainsi que leurs valeurs respectives (10 et 30). En bout de ligne, le système me retourne le nombre de combinaisons possibles qui est de 3 pour la valeur 10 et 14 pour la valeur 30 .

J'ai pas tout expliqué le contexte mais cela ressemble à ça.

**Jedai** · 29/09/2007, 23h02

Alors, voici une solution qui fait de la programmation dynamique en Haskell pour résoudre ton problème, le seul "problème" c'est que le programme fait un usage avancé des valeurs récursives et de l'évaluation paresseuse en Haskell, alors tu auras peut-être un peu de mal à comprendre comment traduire ça dans ton langage (précise le paradigme dans lequel tu travailles et je t'aiderais à traduire) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import System
 
combinations = foldl (\without p ->
                          let (poor,rich) = splitAt p without
                              with = poor ++ 
                                     zipWith (++) (map (map (p:)) with)
                                                  rich
                          in with
                     ) ([[]] : repeat [])
 
main = do
  args <- getArgs
  let n = read $ args !! 0
  print . length $ combinations [2,5,10,13] !! n

Là j'ai codé en dur la liste des valeurs initiales, et tu fournit en arguments le résultat que tu veux obtenir. Mais l'intéressant est la fonction "combinations" qui reçoit en arguments une liste de valeur et te renvoie une liste infinie où à l'index n tu trouves toutes les combinaisons (multi-ensembles, l'ordre ne compte pas, mais on peut avoir plusieurs fois la même valeur) dont la somme donne n.

NB: Cette fonction est relativement efficace, elle ne mettra que quelques microsecondes à résoudre les cas que tu as donné et peut s'étendre à des cas beaucoup plus important (faut pas pousser non plus, la prog dynamique c'est cher en place).

--
Jedaï

**Geno312** · 29/09/2007, 23h09

Merci pour cette solution.

En effet, c'est un peu compliqué à comprendre

Je suis dans l'environnement Java.

**pseudocode** · 30/09/2007, 00h57

Avec une programmation impérative (java), je ne vois pas comment récupérer "seulement" le nombre de combinaisons sans faire une exploration complète des solutions du problème.

Est-ce la traduction du haskell en imperatif fait apparaitre une autre solution ?

**Geno312** · 30/09/2007, 01h13

Le problème s'est que je n'arrive pas à faire la conversion en java à partir de ce langage...

**PRomu@ld** · 30/09/2007, 09h36

hum ... deux map dans un fold left, j'ai bien peur qu'en traduisant le code tu doives faire une exploration complète.

Mais comme tu le proposais au début, en prog dynamique ça doit pouvoir le faire, il faudrait que je regarde de plus près.

*EDIT :

Plutot que de partir de 0, tu peux essayer de partir par x :

Ex x = 10. M = { 2 5 10 13 }

Code :

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

1
2
3
4
5
6
7
 
  10 10 10  10 
   8  5  0   -
   6  0  -   -
   4  -  -   -
   2  -  -   -
   0  -  -   -

Ici, la construction ne fonctionne que pour une suite répétée de Mi (ie: une décomposition avec le même chiffre), mais en répétant le processus en |M| dimensions ça doit pouvoir passer : dans la Mi-ème dimension, tu retranches le Mi-ème terme. Dès que tu as un 0, c'est que tu as une décomposition. Mais a bien y réfléchir (en fait il ne faut pas longtemps

), je ne suis pas convaincu que ça soit une bonne solution ...

EDIT2 :

En travaillant numériquement, il n'y a pas moyen de trouver ça directement ?

De mémoire il y a 2^(n-1) décompositions pour un nombre n :

Ex 4 :

Code :

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

1
2
3
4
5
6
 
4 = 1 + 1 + 1 + 1 
  = 1 + 1 + 2 et 1 + 2 + 1 et 2 + 1 + 1
  = 1 + 3  et 3 + 1
  = 2 + 2
  = 4

En commençant par enlever les combinaisons qui sont les mêmes (1 + 3 et 3 + 1 par exemple), et ensuite en enlevant celles qui ne peuvent pas être générée (parce qu'on a pas les bons nombres), il y a peut-être un moyen de trouver la solution directement ! Amis matheux, au boulot

Au passage : http://fr.wikipedia.org/wiki/Fonctio..._d%27un_entier

**Jedai** · 30/09/2007, 11h53

Envoyé par PRomu@ld

EDIT2 :

En travaillant numériquement, il n'y a pas moyen de trouver ça directement ?

De mémoire il y a 2^(n-1) décompositions pour un nombre n :

En commençant par enlever les combinaisons qui sont les mêmes (1 + 3 et 3 + 1 par exemple), et ensuite en enlevant celles qui ne peuvent pas être générée (parce qu'on a pas les bons nombres), il y a peut-être un moyen de trouver la solution directement ! Amis matheux, au boulot

Il n'y a pas vraiment de formules directes pour le nombre de partage d'un entier (bien qu'il y ait nettement mieux que la récursion simple), de plus il t'a peut-être échappé que le problème présent est un peu plus complexe que cela : les valeurs qu'on peut utiliser pour partager l'entier sont arbitraire, en cela il s'agit d'un problème NP-Complet bien connu (knapsack). Aussi les solutions sont forcément exponentielles dans le cas général.

Je n'avais pas remarqué que tu voulais seulement le nombre de possibilités, dans ce cas le code suivant est de loin préférable pour toi (il est extrèmement plus rapide) :

Code :

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

1
2
3
4
5
6
counter = foldl (\without p ->
                     let (poor,rich) = splitAt p without
                         with = poor ++ 
                                zipWith (+) with rich
                     in with
                ) (1 : repeat 0)

Comme tu peux le voir il procède exactement de la même façon, en utilisant de la programmation dynamique "à la sauce Haskell". Vous pouvez avoir l'impression superficielle que ce code procède du bas vers le haut et construit un tableau du nombres de combinaisons possibles ainsi, mais en réalité ce n'est pas ainsi que cela se passe à l'exécution, grâce à la paresse l'exécution se déroule du haut vers le bas, partant de la valeur demandé et descendant de toutes les valeurs possibles puis recommençant jusqu'à atteindre 0 par l'un quelconque des chemins possibles (mais bien sûr en mémoisant les résultats intermédiaire, sinon ce serait extrèmement inefficace).

En gros, ce dont vous avez besoin pour le faire en paradigme impératif, c'est d'un tableau de la taille de la valeur (ou un hash si tes valeurs initiales sont très clairsemés et/ou grande) et d'une fonction récursive qui utilise ce hash pour mémoiser ses résultats intermédiaires et partant d'une valeur x cherche à connaître quels sont les combinaisons possibles donnant x en additionnant l'ensemble des combinaisons possibles pour x-2, x-5, x-... .
Attention, pour bien obtenir le nombre de multi-ensembles et pas seulement celui des n-uplets, il est important que cette fonction récursive ne puisse essayer -2 après avoir déjà essayé -5 (ou -10, ou -13) auparavant.

Suis-je clair ? (probablement pas vraiment, mais en faisant un petit effort tu y arriveras, d'autant que knapsack est un exemple canonique de programmation dynamique)

EDIT : En fait il s'agit ici de subset-sum plutôt que de knapsack, bien que l'un puisse être vu simplement comme une instance de l'autre. En fait vu que tu veux compter le nombre de possibilité, tu es forcément en exponentiel, ce n'est même pas une question !!

--
Jedaï

**pseudocode** · 30/09/2007, 13h10

Envoyé par PRomu@ld

hum ... deux map dans un fold left, j'ai bien peur qu'en traduisant le code tu doives faire une exploration complète.

oui, c'est bien ce que je me disais... Avec la contrainte "decomposition en nombres croissants", je n'ai meme pas trouvé comment ecrire le code avec une recursion terminale... C'est trop dur pour un dimanche.

Code java :

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
public class Packing {
 
	static int[] SET;
 
	/**
         * @param M la valeur a atteindre
         * @param index l'index de debut dans le SET
         * @return le nombre de decomposition
         */
	static int decomposition(int M, int index) {
		// conditions d'arret
		if (M==0) return 1;  // trouvé
		if (M<0) return 0;   // on a dépassé la valeur a atteindre
		if (index>=SET.length) return 0; // on n'a plus de choix possible
 
		int n=0;
		// nombre de combinaisons en prenant le 1er element du SET
		n+=decomposition(M-SET[index], index);
		// nombre de combinaisons sans prendre le 1er element du SET
		n+=decomposition(M, index+1);
		return n;
	}
 
	public static void main(String[] args) {
		SET = new int[] {2,5,10,13};
		System.out.println("F(10) = " + decomposition(10, 0) );
		System.out.println("F(30) = " + decomposition(30, 0) );
	}
}

Résultat:

F(10) = 3
F(30) = 14

Envoyé par Jedai

En gros, ce dont vous avez besoin pour le faire en paradigme impératif, c'est d'un tableau de la taille de la valeur (ou un hash si tes valeurs initiales sont très clairsemés et/ou grande) et d'une fonction récursive qui utilise ce hash pour mémoiser ses résultats intermédiaires (...)

Effectivement en utilisant un "cache" des valeurs déja calculées on diminue grandement le nombre de boucle. Dans l'exemple Java précédent (F(10) puis F(30)) on passe de ~300 appels a ~100.

**Jedai** · 30/09/2007, 15h55

Envoyé par pseudocode

Effectivement en utilisant un "cache" des valeurs déja calculées on diminue grandement le nombre de boucle. Dans l'exemple Java précédent (F(10) puis F(30)) on passe de ~300 appels a ~100.

C'est même complètement indispensable pour les plus grandes valeurs (30 est minuscule).

Par ailleurs tu ne peux probablement pas transformer ce programme en récursion terminale (sans utiliser une pile par ailleurs pour simuler une vraie récursion), je ne pense pas que ce soit une fonction récursive primitive.

--
Jedaï

Envoyé par pseudocode

oui, c'est bien ce que je me disais... Avec la contrainte "decomposition en nombres croissants", je n'ai meme pas trouvé comment ecrire le code avec une recursion terminale... C'est trop dur pour un dimanche.

Néanmoins je le répète, ce code en Haskell n'effectue pas une exploration complète, grâce à l'évaluation paresseuse elle est en fait aussi efficace que ta solution Java (avec un cache rajouté) du point de vue complexité.
Notez que "counter [1..300] !! 3000" s'exécute en moins d'une seconde (en mode interprété) et donne le résultat 479760613336762496008428480167132601531720634630249319351 (

), je m'attend à des performances comparable d'une implémentation Java avec mémoisation (tu peux confirmer Pseudocode ?), cela sera-t-il suffisant comme performance pour ton problème ?

--
Jedaï

**pseudocode** · 30/09/2007, 18h04

Envoyé par Jedai

Notez que "counter [1..300] !! 3000" s'exécute en moins d'une seconde (en mode interprété) et donne le résultat 479760613336762496008428480167132601531720634630249319351 (

), je m'attend à des performances comparable d'une implémentation Java avec mémoisation (tu peux confirmer Pseudocode ?)ï

heu... non.

1. Deja, moi je trouve 48696247. Tu es sur que ton code gere les doublons ? (Tu trouves bien 14 pour [2,5,10,13] !!30 ?)

2. Ca prend 2.7s avec le cache. Sans le cache, j'ai abandonné (

). Bon, on doit pouvoir tomber sous les 2.7s en utilisant autre chose que la HashMap du JDK pour faire un cache. Java c'est leeeeeeent.

**Jedai** · 30/09/2007, 18h25

Envoyé par pseudocode

heu... non.

1. Deja, moi je trouve 48696247. Tu es sur que ton code gere les doublons ? (Tu trouves bien 14 pour [2,5,10,13] !!30 ?)

Oui, je trouve bien 14, mais réfléchis un peu, ton nombre ne te semble-t-il pas un peu petit... Essaie "counter [1..90] !! 90" (autrement dit le nombre de combinaisons pour faire 90 avec les nombres de 1 à 90), normalement tu devrais déjà trouver plus que 48_696_247 !!

Je te suggère de reréfléchir au fait que 48_696_247 est inférieur à 2^32 - 1...

Bon, on doit pouvoir tomber sous les 2.7s en utilisant autre chose que la HashMap du JDK pour faire un cache. Java c'est leeeeeeent.

Bah forcément si tu utilises un HashMap dans cette situation... Il vaut mieux utiliser un tableau dans ce cas puisque les valeurs sont petites, toutes les cases du tableau serviront.
(En fait ici Haskell prend 0.8s pour donner la réponse en utilisant une bête liste chainée)

--
Jedaï

**pseudocode** · 30/09/2007, 19h00

Envoyé par Jedai

Je te suggère de reréfléchir au fait que 48_696_247 est inférieur à 2^32 - 1...

c'est pas faux...

Bah forcément si tu utilises un HashMap dans cette situation... Il vaut mieux utiliser un tableau dans ce cas puisque les valeurs sont petites, toutes les cases du tableau serviront.
(En fait ici Haskell prend 0.8s pour donner la réponse en utilisant une bête liste chainée)

Oui, la hashmap c'etait juste pour me simplifier la vie. J'ai donc mis un tableau... résultat:

F(3000) = 79760613336762496008428480167132601531720634630249319351
time: 2016 ms

c'est clair que ca vaut pas le lazy-evaluation.

**Jedai** · 30/09/2007, 19h52

Envoyé par pseudocode

c'est pas faux...

Oui, la hashmap c'etait juste pour me simplifier la vie. J'ai donc mis un tableau... résultat:

F(3000) = 79760613336762496008428480167132601531720634630249319351
time: 2016 ms

c'est clair que ca vaut pas le lazy-evaluation.

J'aimerais bien avoir ton code, pour le tester sur mon ordinateur pour voir.

De mon côté j'ai ce code :

Code Java :

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
import java.math.BigInteger;
import java.util.Arrays;
 
public class Packing {
 
	/**
         * @param M la valeur a atteindre
         * @param SET les valeurs utilisables
         * @return le nombre de decomposition
         */
	static BigInteger decomposition(int M, int[] SET) {
		BigInteger[] results = new BigInteger[M+1];
		Arrays.fill(results, BigInteger.ZERO);
		results[0] = BigInteger.ONE;
		for(int i : SET){
			for(int j = i; j < M+1; j++){
				results[j] = results[j].add(results[j-i]);
			}
		}
		return results[M];
	}
 
	public static void main(String[] args) {
		int[] set = new int[300];
		for(int i=0; i<300; i++) set[i] = (i+1);
		long start = System.currentTimeMillis();
		System.out.println("F(3000) = " + decomposition(3000, set ));
		System.out.println("Time elapsed = " + (System.currentTimeMillis() - start));
	}
}

Avec comme résultat :

F(3000) = 479760613336762496008428480167132601531720634630249319351
Time elapsed = 391

Il est probable que selon les ensembles de valeurs de départ, l'une ou l'autre de ces approche soit plus ou moins efficace, la version Haskell par contre devrait adapter sa stratégie selon les ensembles de départ (elle donne par exemple de meilleurs résultat sur un ensemble comme {181,203,345,456,678} pour de grosses valeurs comme 300000).

--
Jedaï

**pseudocode** · 30/09/2007, 23h45

De mon côté j'ai ce code :

Excelent code.

Sans doute le meilleur qu'on puisse ecrire pour résoudre ce probleme. C'est la traduction 'au plus proche' de ton programme Haskell ? (faut vraiment que je trouve le temps d'apprendre ce langage

)

J'en avais fait une version equivalente en suivant les indications de wikipedia (cf lien de Promu@ld).

Code java :

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
 
static BigInteger[] buildResults(int X, int[] SET) {
	BigInteger[] F=new BigInteger[X+1];
	Arrays.fill(F,BigInteger.ZERO);
	// mise a jour de F(k) pour chaque element du SET
	for(int s:SET) {
		// si k<s, alors F(k)=0.
		// si k=s, alors F(k)=1
		// si k>s, alors F(k)=F(k-s)
		F[s]=F[s].add(BigInteger.ONE);
		for(int k=s+1;k<=X;k++)	F[k]=F[k].add(F[k-s]);
	}
	return F;
}
 
public static void main(String[] args) {
	int[] SET = new int[300];
	for(int i=0;i<SET.length;i++) SET[i]=i+1;
	int X=3000;
	BigInteger[] F = buildResults(X,SET);
	System.out.println("F(3000) = "+F[3000]);
	System.out.println("Time: "+(t1-t0)+" ms");
}

Envoyé par Jedai

J'aimerais bien avoir ton code, pour le tester sur mon ordinateur pour voir.

Bof. Tu vas etre déçu. C'est l'approche recursive classique avec un simple cache (clé->valeur).

Code java :

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
 
import java.math.BigInteger;
import java.util.Arrays;
 
public class TestPacking {
 
	static int[] SET = null;
 
	// ---------- Cache d'evaluation ----------
 
	static BigInteger[] cache = null;
 
	static void initCache(int X)  {
		cache = new BigInteger[X*(SET.length+1)+SET.length];		
	}	
	static BigInteger getFromCache(int M, int index)  {
		int hash = M*(SET.length+1)+index;
		return cache[hash];
	}
	static void putInCache(int M, int index,BigInteger value)  {
		int hash = M*(SET.length+1)+index;
		cache[hash]=value;
	}
 
	// -----------------------------------------
 
	/**
         * @param M      la valeur a atteindre
         * @param index  l'index de debut dans le SET
         * @return       le nombre de decomposition
         */
	static BigInteger decomposition(int M, int index) {
		// conditions d'arret
		if (M == 0) return BigInteger.valueOf(1); // trouvé
		if (M < 0)  return BigInteger.valueOf(0); // on a dépassé la valeur a atteindre
		if (index >= SET.length) return BigInteger.valueOf(0); // on n'a plus de choix possible
 
		// déja évalué ?
		BigInteger n=getFromCache(M, index);
		if (n!=null) return n;
 
		// nombre de combinaisons en prenant le 1er element du SET
		n=decomposition(M - SET[index], index);
 
		// nombre de combinaisons sans prendre le 1er element du SET
		n=n.add( decomposition(M, index + 1) );
 
		// ajout au cache d'evaluation
		putInCache(M, index, n);
 
		return n;
	}
 
	public static void main(String[] args) {
		SET = new int[300];
		for(int i=0;i<SET.length;i++) SET[i]=i+1;
 
		int X=3000;
 
		long t0 = System.currentTimeMillis();
		initCache(X);		
		BigInteger result = decomposition(X, 0);
		long t1 = System.currentTimeMillis();
 
		System.out.println("F(3000) = "+result);
		System.out.println("Time: "+(t1-t0)+" ms");
	}
}

**Jedai** · 01/10/2007, 00h35

Envoyé par pseudocode

Sans doute le meilleur qu'on puisse ecrire pour résoudre ce probleme. C'est la traduction 'au plus proche' de ton programme Haskell ?

Et bien ça ressemble beaucoup à ce que fait le programme Haskell, mais ce n'est que partiellement vrai, car la fonction Haskell n'effectue pas forcément toutes les additions qu'effectue le programme Java, elle n'évalue vraiment que celle qu'elle a besoin d'évaluer pour obtenir le résultat, à cause de l'évaluation paresseuse. C'est pourquoi sous certaines conditions (cf l'exemple dans mon dernier post) il recommence à dépasser le programme Java malgré le lourd handicap de l'évaluation paresseuse (si au final on évalue tout, la paresse est une perte nette forcément, comme dans le cas du [1..300] pour 3000) et de la structure de donnée plus lourde (liste chaînée au lieu de tableau).

L'argument que l'évaluation paresseuse accélère les programmes est souvent mésusé, si l'algorithme strict est bien pensé, il ne fait pas de chose inutile et l'évaluation paresseuse devient une surcharge. Mais le vrai avantage de l'évaluation paresseuse c'est la modularité facile et élégante qu'elle apporte, comme ici, où la fonction Haskell renvoie une liste infinie qu'il est bien plus facile d'utiliser comme cache temporaire auquel on peut demander n'importe quelle valeur (l'équivalent Java demanderait de coder un objet contenant le set des valeurs initiales et une List de nombre de combinaisons s'étendant à la demande...). De plus j'ai déjà souligné le fait que la fonction Haskell s'adaptait plus facilement à différents scénarios (beaucoup de petits nombres, quelques gros nombres, etc...).

--
Jedaï

Envoyé par pseudocode

Bof. Tu vas etre déçu. C'est l'approche recursive classique avec un simple cache (clé->valeur).

C'est une approche plus effective sur certains set de données, par exemple sur {181,203,345, 456, 678} -> 300000, cette approche est plus rapide que celle basé sur un tableau exhaustivement calculé. Sur cet exemple elle est à peu près aussi rapide que le Haskell.

Egalement ma machine étant un peu plus rapide que la tienne, cette version ne prend que 1,2s pour le {1..300} -> 3000.

--
Jedaï