Discussion :

[Morvan Mikael]

Salut à tous,

J'ai un algorithme d'optimisation à trouver pour mon client et il me faut trouver toutes les combinaisons possibles d'une suite d'éléments. Ca revient à faire des Anp et des Cnp (dur à écrire).
Je connais la formule pour trouver les nombres correspondants mais j'aimerai surtout avoir l'algorithme qui me fait ça.
En clair, j'ai un tableau de p éléments et je voudrai trouver toutes les possiblités d'ordonner n éléments parmis ces p éléments.

Merci de vos réponses.
Mikaël Morvan

[delphi-fan]

C'est vraiment trivial :

Anp = n! / (n-p)! et Cnp = Anp / p!

où ! signifie factorielle.

on rappèlle : n! = n x (n-1) x (n-2) x .... x 1
ex : 4! = 4 x 3 x 2 x1 = 24.

Il doit exister une fonction toute prête qui calcule la factorielle. Sinon tu peux la programmer facilement: c'est l'exemple basique d'une fonction récursive , mais tu peux aussi le faire par une boucle for i:=1 to n do total = total * n (attention aux initialisations !)

A+

[Morvan Mikael]

C'est bien ce que j'ai dit ==>

Je connais la formule pour trouver les nombres correspondants mais j'aimerai surtout avoir l'algorithme qui me fait ça.

C'est l'algorithme qui va me donner les n éléments parmis les P que je veux.

Donc si j'ai une tableau de 3 éléments E1, E2 et E3 et que j'en veux 2. Je veux trouver l'algorithme qui va me donner:
E1E2, E1E3, E2E1, E3E1, E2E3 et E3E2...

Les Cnp et Anp ne me sont pas du tout inconnus mais ce n'est pas ça qui m'intéresse...

A+

[delphi-fan]

Excuses moi, je n'avais pas bien compris.

Pour ce qui est de l'algorithme, je l'ai déjà utilisé mais je ne l'ai pas là sous la main. Je le rechercherais ce soir.

Ce que je peux te dire, c'est qu'il est basé sur une procédure récursive qui explore toutes les feuilles de l'arbre binaire et qui construit, en fonction de tes données de base (E1, E2, ...) une chaîne, du type Chaîne := Chaîne (ex:E1) + valeur testée (ex:E2) = E1E2 -> nouvelle récursion -> E1E2E3 ... Après traitement, on ressort de la boucle récursive et on se retrouve avec Chaine = E1 -> E1E3 -> niveau suivant etc ...

Si tu peux donner l'exemple complet et si tu as la patience d'attendre un jour ou deux, tu auras le code entier.

A+

[Morvan Mikael]

Merci, je peux être patient

Par contre, mon problème n'est pas un arbre binaire mais un arbre planaire... Un peu plus compliqué

Pour information voici la demande de mon client:

Le but est de faire une répartition de puissance à l'aide de combinaison de boites de jonction.
J'ai des boites de jonctions qui font la séparation de la puissance en entrée vers n sorties. La répartition n'est pas forcément linéaire (1 vers 1/2 1/2 ou 1 vers 1/3 2/3). On peut empiler autant de boites de jonction que l'on veut. Toutes les boites de jonctions sont connues d'avance. Le nombre maximum de sortie est de 16.

Voila en gros mon cauchemar actuel... S'il y a des solutions ou au moins des liens vers lesquels me tourner...

Merci d'avance,
Mikaël Morvan

[delphi-fan]

Désolé, mais il me faut d'autres précisions, dans la mesure où je ne connais rien en électricité ...

Schématiquement, je cherche à modéliser ton problème sous forme d'arbre (pas binaire bien sûr : ah écrire sans réfléchir ... ) et à explorer les branches en profondeur puis réaliser un backtracking.

Ce que je ne sais pas avec les informations que tu me donnes (et c'est vital pour le problème) c'est :
- quel est le résultat auquel on doit arriver (ex : c'est comme si tu me disais j'ai une équation X * Y = 12 -> ok je peux explorer sur X et Y) : est-ce un calcul de puissance (P=U*I) ...car je ne ne comprends pas tes 1 vers 1/2 etc.
- Y a-t-il un seul résultat possible ?
- Doit-on rechercher une solution avec le maximum théorique de boites de jonctions (contrainte) ou est-ce libre ?
- Si plusieurs résultats, faut-il s'arrêter au premier valide ou lister exhaustivement tous les cas possibles ?

Merci de ta réponse....

A+

[Morvan Mikael]

Merci de ta patience

Le résultat auquel je dois arriver est une combinaison de boites donnant pour leurs sorties des puissances correspondant à ce qui est demandé. Par exemple, mon client veut une répartition en puissance de 6 éléments : {5,6,7,4,8,10}.
Dans ce cas, on peut proposer soit une boite de jonction 1 vers 6 avec les puissances correspondantes si elles existent ou bien 3 boites (1 de 1 vers 2 et 2 de 1 vers 3).

Donc on voit bien qu'on aura pas une solution unique mais plutôt un ensemble de solutions qu'on pourra noter pour estimer laquelle est la meilleure.
On peut donc à mon avis parcourir l'ensemble de l'arbre des solutions et donner uniquement les solutions correspondants à un critère de compatibilité.

Voila, si tu as d'autres questions n'hésite pas. (Aujourd'hui je suis en formations toute la journée donc je ne pourrais pas te répondre avant 12h00)

Merci encore,
Mikaël Morvan

[delphi-fan]

Ayant l'impression d'être un parfait idiot, j'ai demandé des précisions dans ma boite à 2 techniciens et 1 ingénieur. Résultat : ils sont eux aussi dans le vague quant à tes explications.

Je te demanderais donc de fournir un exemple exhaustif (genre l'électricité pour les nuls) avec la puissance d'entrée, les puissances à obtenir en sortie, le mode de calcul de la puissance (additif / multiplicatif entre brins et boites) . Pour effectuer une simulation de l'algorithme, n'hésite pas à fixer le nombre et les caractéristiques des boites possibles à employer et précise les calculs de ventilation de la puissance d'entrée à chaque stade (boite de jonction)...

Merci et A+

[Morvan Mikael]

Désolé pour mon explication, je suis trop dans le métier du client maintenant

Je vais tenter d'expliquer par un schéma ce que je veux:

Problème général:
Pour alimenter des antennes, on a besoin d'alimenter ces antennes à partir d'une source d'alimentation unique pour des raison de déphasage. Comme les antennes doivent malgrès tout avoir des puissances disctinctes, on est obligé de répartir la puissance en entrée. Cette puissance peut être répartie par l'intermédiaire de boites de jonctions qui répartissent la puissance en entrée vers des puissances en sorties. L'entrée est unique par contre il peut y avoir jusqu'à 16 sorties. La répartition sur les sorties n'est pas équirépartie (1 puissance en entrée ne correspond pas à 1/Nombre de sortie par sortie). Par contre toutes les possibilités de répartition en puissance sont connues.

Explication schématique

Répartition en puissance souhaitée:

6 6 6 4 4

Exemple de répartition des boites de jonction par niveau

| | | | |
1/3 1/3 1/3 1/2 1/2

| |
1/2 1/2
|

Voilà. Cette répartition permet de trouver la répartition en puissance désirée. Le but étant de déterminer la répartition des boites de jonctions pour n répartion de puissance. La limite des sorties est de 48.

Merci encore pour ton aide.

[Sarbacane]

...Je connais la formule pour trouver les nombres correspondants mais j'aimerai surtout avoir l'algorithme qui me fait ça.

C'est un vrai casse- tete en informatique. Il s'agit en general d'implementer N (= taille du/des N-uplets) boucles imbriquees permettant de visiter incrementalement un dictionaire/lexique(=ton tableau).
Example

Code :

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

1
2
3
4
5
6
 
For a1 = 0, 1, ..., m1-1  do
  For a2 = 0, 1, ..., m2-1 do
    For a2 = 0, 1, ..., m3-1  do 
      For a4 = 0, 1, ..., m4-1 do
         Visit (a1; a2; a3; a4);

Cette methode est gourmande mais intuitive et efficace pour de petites valeures de mj et N.

Le PRE-FASCICLE 2A du "THE ART OF COMPUTER PROGRAMMING .. GENERATING ALL n -TUPLES " est une bonne referance. Tu peux le trouver ici. http://sunburn.stanford.edu/~knuth/taocp.html

bonne chance
Sarbacane!

[Morvan Mikael]

Merci de ta réponse mais je ne sais pas par avance combien de combinaisons j'aurai donc je ne sais par par avance combien d'imbrication il faut effectuer.

[jcr]

Bonjour,

j'ai une solution qui pourrai fonctionner sur un table de maximum 9 éléments, mais qui n'est pas très belle.

Si j'ai bien compris, tu connais le nombre d'éléments et le nombre à sélectionner. Voilà l'algo que j'ai pensé :

départ = 10^(nbre chiffre tableau - 1) + 1 //(1)
fin = départ * nbre chiffre tableau // (2)
Pour i=depart jusque fin
Décompose(départ,chaine) // (3)
Si doublon(chaine) // (4)
alors boucle suivante
sinon AfficherRésultat(chaine) // (5)
fin pour
.

Prenons ton exemple avec E1E2E3 dans lequel tu ne veux que 2 éléments.

(1) : je démarre à 11

(2) : la fin est 33 car c'est le dernier cas possible en ayant E3 au début.
E3, E3E1, E3E2, E3E3

(3) : Décompose(départ,chaine) : me tranforme mon nombre décimal en chaine de caractère.

(4) : doublon(chaine) vérifie si j'ai 2 fois le même chiffre dans la chaine, si tu ne peux avoir ce cas (E3E3), il faut éjecter cette possibilié

(5) AfficherRésultat(chaine), parcoure la chiane et ce sert de chaque caractère comme indice dans ton tableau. Il faut vérifier si l'indice n'est pas hors des limites de ton tableau .

Exemples :

11 : /
12 : E1E2
13 : E1E3
14 : /
...
20 : /
21 : E2E1
22 : /
23 : E2E3
24 : /
..
31 : E3E1
32 : E3E2
33 : /

En espérant t'avoir aidé.

A+

[delphi-fan]

Ce code est intéressant d'un point de vue didactique, car il essaye de modéliser le "vecteur d'état" (c'est à dire le cas étudié) d'une façon pratique.
Cela dit, il est sommaire car il ne permet pas d'aller au delà de 9, alors que le sujet peut prévoir jusqu'à 16 boites et 48 sorties ! De plus, on peut trouver des solutions à 3 boites (->E1E2E3 dans ton prog) mais aussi avec 4 ; 5 etc... , ce qui oblige à faire une boucle hiérarchique en plus. Mais il peut être modifié...

Toutefois, l'important n'est pas là : dans la recherche des solutions, que celle-ci se fasse par une boucle traditionnelle, par récursion, par systèmes d'équations ou par la théorie des graphes, il faut absolument que l'objectif soit bien précisé et que l'on puisse donc tester et éliminer des cas, ou au contraire les conserver.

Deux points me gênent particulièrement pour la recherche de l'algorithme :

Répartition en puissance souhaitée:
6 6 6 4 4
Exemple de répartition des boites de jonction par niveau
| | | | |
1/3 1/3 1/3 1/2 1/2
| |
1/2 1/2
|

Doit-on comprendre que la puissance de chacune des sorties est 6 6 6 4 4 ou comme je le pense : 1/6 1/6 1/6 1/4 1/4 de la puissance initiale en entrée ?
Si mon hypothèse est la bonne, on remarque qu'au niveau final, la somme de toutes les répartitions donne bien 100% . De plus, chaque "boite" elle-même respecte la règle des 100% (1/2 + 1/2 = 1 ou 1/3 + 1/3 + 1/3 =1 pour une autre boite)...
=> L'algorithme (à développer) devra tenir compte du fractionnement de la puissance de telle sorte que l'on retrouve en sommant les feuilles la valeur 1 (100%) .

Par exemple, mon client veut une répartition en puissance de 6 éléments : {5,6,7,4,8,10}.

Ici, ce cas ne cadre pas ? avec mon explication précedente, mais il n'est peut-être pas exact (à préciser).
Toutefois, il soulève un problème d'ordre théorique : par multiplication successive de coefficients, des nombres tels que 1/7 peuvent difficilement s'obtenir. Dès lors, la somme des cas possibles risque de ne pas aboutir à 1 (100%) exactement : d'après les techniciens que j'ai consultés, la puissance finale désirée n'est pas toujours exacte, et l'on tolère des variations en plus ou en moins selon les cas de plusieurs % (exemple : 20% dans un cas que l'on m'a cité).
Je te laisse imaginer que cela peut poser un problème délicat pour la condition de succès d'une combinaison.

Si tu pouvais donc me préciser ces deux points, on pourrait alors se lancer à la recherche d'un algorithme efficace avec toutes les données du problème .

A+

[Morvan Mikael]

Oui effectivement, la somme des puissances en sortie est la puissance d'entrée. Par contre, ma notation entière est valide car on peut parler de part de la puissance globale pour chaque sortie. C'est juste un moyen de ne pas se trimbaler des chiffres décimaux.
De plus, ce que je cherche à obtenir n'est pas la composition exacte mais une liste de solutions approchées avec une notation pour chaque solution. L'utilisateur pourra ensuite choisir suivant le cas et suivant sa connaissance métier l'une des solutions proposées.

Voilà, j'espère que ces explications sont suffisantes. N'hésite pas à poser d'autres questions.

Merci encore,
Mikaël Morvan

[olivieram]

Mikael,

si j'ai bien compris, tu veux un algo qui te donne le nombre et la
suite des possibilités qu'il y a de répartir la période N sur P composants.

Des applications de ce type:
- L'équation d'une onde (calculx aux limites, points singuliers)
- une série (convergence vers 1, résidus, développements limités)

Autre application ... ++ simple

J'ai des pièces de 1,2,5 et 10 euros. Je veux connaitre l'ensemble
des combinaisons de ces pièces pour faire 100 euros.
-----------

L'algo aura la propriété suivante :

Le nombre de possibilités est égal à la complexité de la fonction de recherche de ces possibilités

Voici donc un algorithme dont la complexité (ici en nombre d'appels) est égale au nombre de possibilités:
La fonction prend en entrée:

• la somme N à calculer
  P le poids courant
  T le tableau trié par ordre décroissant des poids de chaque pièce

La fonction retourne le nombre de possibilités.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
fonction monnaie(N,P) retourne POSS
   Si N=0 alors POSS = POSS + 1
   sinon
         Pour toute pièce E dans T inférieure ou égale à P
              Si E <= N alors
                      monnaie(N-E,E)
              Fin Si
              POSS = POSS + 1
         Fin Pour
   Fin Si
Fin

Pour connaitre les possibilités, il sufft de conserver un tableau de taille variable et de l'afficher seulement quand N=0

PS: toujours s'arranger pour que N arrive à 0.

Complètons l'algorithme en disant qu'il faut l'ensemble des combinaisons qui utilisent exactement K pièces.

Code :

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
 
fonction monnaie(N,P,K) retourne POSS
   Si N=0 alors POSS = POSS + 1
   Sinon
         Pour toute pièce E dans T inférieure ou égale à P
              Si K=1 alors
                     Si E = N alors
                             monnaie(0,E,0)
                     Fin Si
              Sinon
                     Si E < N alors
                             monnaie(N-E,E,K-1)
                             POSS = POSS + 1
              Fin Si
         Fin Pour
   Fin Si
Fin

[Morvan Mikael]

Merci pour ta contribution, je vais l'essayer dès que possible et je donnerai des nouvelles...

Merci encore,
Mikaël Morvan

[ffozeu]

Salut Mikaël Morvan

Si tu n'as pas encore eu de solution à ton problème, tu peux regarder ce site:

http://jean-paul.davalan.pagesperso-...arr/index.html

J'avais le même souci et je suis tombé dessus. j'ai pu analysé le js pour écrire deux fonctions php donc le code est le suivant:

private function arrgt($L, $t, $n ,$k) {
global $arrgtliste, $nbarrgt;
if($k==0) {
$arrgtliste []= "(".$L.") ";
$nbarrgt++;
} else {
for($i=0;$i < $n; $i++) {
$L2 = $L . $t[$i];
if($k>1) $L2 .= ", ";

$t2 = array();
$j = 0;
for($r = 0 ; $r < $n ; $r++) {
if($r != $i) {
$t2[$j] = $t[$r];
$j++;
}
}
$this->arrgt($L2, $t2, $n-1, $k-1);
}
}
}

private function effectue($ens,$k,$n=4) {
global $arrgtliste,$nbarrgt;
$L = "";
$t = array();
for($i=0; $i<$n; $i++)
$t[$i] = $ens[$i];

$arrgtliste = array();
$nbarrgt = 0;
$this->arrgt($L, $t, $n, $k);
var_dump($arrgtliste);
var_dump($nbarrgt);
}

Bien entendu je suis dans une classe php.

je te laisse regarder!