Partition à l'aide de combinaisons

[kaderben]

Bonjour
Soit les points suivants affectés chacun d'un nombre entier:
A(26),B(20),C(6),D(15),E(7),f( 4),...,N(4).
Le but est d'énumérer tous les n-uplets (en terme de combinaisons et non arrangements)dont la somme ne dépasse pas 25:
tous les couples dont la somme des deux nombres ne dépasse pas 25, tous les triplets dont la somme ne dépasse pas 25, tous les quadruplets dont la somme ne dépasse pas 25 etc...
exemple: CD(21), CEF(17), CEFN(21) etc...
Voici l'algorithme que j'ai choisi:les tableaux à 2 entrées
Pour les couples
1° ligne: les points et leur nombre
1°colonne:les points et leur nombre et on fait la somme des nombres

Pour les triplets:
1° ligne: les couples et leur nombre
1°colonne:les points et leur nombre et on fait la somme des nombres

Pour les quadruplets:
1° ligne: les triplets et leur nombre
1°colonne:les points et leur nombre et on fait la somme des nombres
etc...
Bien sûr dans chaque uplet, un point doit figurer au plus une fois car ce sont des combinaisons et non des arrangements.
Question:
1°) Est ce qu'on risque d'oublier des combinaisons ?
2°) Y'a t-il pas un autre algorithme plus simple et efficace; car celui là est fastidieux...(on en a pour des heures!).
Merci pour vos conseils.
-----

[KerLannais]

Salut,

Il me semble que ton problème (puisque tu considère des combinaisons et non des arrangements) est le problème du sac à dos. Tu peux regarder la page
http://fr.wikipedia.org/wiki/Problème_du_sac_à_dos
Par ailleurs, ce problème est abondamment traité dans la littérature en informatique théorique.

[KerLannais]

Non autant pour moi, le problème du sac à dos ne s'intéresse pas au nombre de solutions possibles.

Dans tes exemples tu ne prends jamais un point plusieurs fois, est-ce que cela fait partie des règles? Par ailleurs des points différents on la même valeur, apparamment tu comptes CEN et CEF comme deux combinaisons différentes. Dans ce cas, le nombre de combinaison se déduit facilement du nombre d'arrangement, il suffit de diviser par avec le nombre d'objet dans l'arrangement puisque aucun objet n'est répété deux fois. Le nombre d'arrangement étant lui facile à déterminer par programmation dynamique en utilisant qu'un seul tableau. La complexité est alors raisonnable.

[kaderben]

peut être que je ne me suis pas fait comprendre:
1°)Les points ayant la même valeur et un point ne se répète pas dans une combinaison font partie de la règle
2°) il ne s'agit pas de déterminer le nombre de possibilités mais de les écrire toutes, c'est à dire tous les couples ,triplets etc...(combinaisons) dont la somme ne dépasse pas 25.
3°) Je ne sais pas ce que c'est "la programmation dynamique en utilisant qu'un seul tableau".
Merci

[A voir en vidéo sur Futura]

[KerLannais]

Ok

Notons tes points et les valeurs associées qui sont des entiers naturels non nuls pas nécessairement deux à deux distincts si j'ai bien compris. Notons l'ensemble des -uplets ne contenant que des points parmis la liste dont la somme des valeurs associées est inférieur ou égale à . Les -uplets étant classés à l'ordre près on peut supposer que les points qu'il contient sont rangés par ordre croissant des indices. Exemple



On ne peut pas utiliser puisqu'on a pris , on ne compte pas parce que ses points ne sont pas rangés par ordre croissant des indices et a une somme égale à ce qui est strictement supérieur à .
notons la fonction qui a un point et à un -uplet associe le -uplet dont la première composante est et dont les suivantes sont celles de .
On a la relation de récurrence suivante

sachant que

si ou et que par ailleurs les sont faciles à déterminer. Pour implémenter un algorithme il faut créer un tableau à trois entrées dont les éléments sont des ensembles (ou listes) de -uplets. Les dimensions sont
, et
avec la taille maximal des -uplets que l'on considère. Au départ chaque case du tableau contient un symbole qui signifie que l'ensemble correspondant à la case n'a pas encore été calculé. On veut calculer un certain , en appliquant les formule on voit qu'il faut calculer certains il s'agit donc d'un certain arbre à parcourir (par un parcours en profondeur) quand on arrive au feuilles (cas d'indices extrèmes ou ou ) on peut calculer les correspondant et on rempli le tableau on peut alors calculer les noeuds à l'étage au dessus des feuilles, puis à l'étage encore au dessus et etc sans recalculer des noeuds (qui correspondent à des cases du tableau) qui ont déjà été calculés, jusqu'à arriver au sommet, le que l'on voulait calculer au départ.

Sur mon exemple, je veux calculer

l'ensemble des triplets dont la somme est inférieure ou égale à
la formule dit que je doit calculer
, et
(puisque )
Pour calculer il faut calculer


on en déduit

Pour calculer il faut calculer
puisque
donc
Enfin on a directement . On en déduit

Il n'y a pas d'algorithme plus efficace étant donné que le nombre d'étape n'est pas supérieur au nombre de solution que l'on énumère, un algorithme plus rapide ne peux qu'oublier des solutions.

[kaderben]

Merci KerLannais pour le cours et l'exemple, j'ai compris.
Pour l'exemple, t'as créé un tableau à 3 entrées ou non pour le faire?
Merci

[KerLannais]

Oui, l'idée d'avoir un tableau à trois entrées c'est pour prendre en note les déjà calculés afin de ne pas les recalculer mais par contre on ne les calcule pas tous loin de là, on part de celui que l'on veut calculer et on calcule tous ceux dont on a besoin, ce qui permet un gain d'efficacité. Il est facile dans n'importe quel langage de programmation de créer des tableaux à trois entrées mais c'est bien sûr plus difficile si on veut programer l'algorithme sur une page excel. Si on veut appliquer l'algorithme à la main il suffit de tracer un arbre, et de garder une trace des ensembles que l'on calcule. Dans le cadre d'un programme on peut aussi faire une liste des ensembles calculés et à chaque fois chercher dans la liste si un ensemble a été calculés mais c'est moins efficace