Algorithme combinaison maths !!! Au secours...

[unlu]

Bonjour,

j'essaye depuis cet après midi à résoudre un problème d'algorithme de combinaisons mathématiques.

Objectif: créer une fonction qui pour un tableau donné retourne un tableau contenant les différentes combinaisons du tableau de départ.

Pour être plus précis :
mon tableau de départ appelé TabDepart est un tableau de dimensions n*m (n lignes et m colonnes). Chaque case de ce tableau peut avoir 1 seule valeur booléenne 0 ou 1.
V i € N, V j € N, i<=n, j<=m, TabDepart(i,j) = 0 ou 1.

Chaque colonne représente en fait selon son indice une lettre de l'alphabet, par exemple la colonne 0 représente la lettre "A", 4 le "E" etc...
Si la valeur d'une case dans le tableau de départ est égale à 0, cela veut dire que la lettre ne doit pas être affichée parmi les combinaisons du tableau final, dans le cas contraire il doit être affiché.

Si on prend un exemple concret :
Supposons que le tableau (3*3) ci-dessous représente notre tableau de départ avec les valeurs suivantes :
(A B C)
1 0 1
0 1 1
1 1 1

Notre tableau final doit alors afficher ceci :
A B A
A B B
A B C
A C A
A C B
A C C
C B A
C B B
C B C
C C A
C C B
C C C

C'est un vrai casse tête pour moi j'éspère qu'il y 'a des matheux parmi vous...


Merci !

[loobot]

langage ?

[unlu]

Ah oui excusez moi,
C'est du PHP classique !!!

[unlu]

Personne pour résoudre ce fichu problème ???

[pascal_]

Essaye de développer un peu ton exemple, j'ai rien compris à ce que tu faisais...

[Tisha]

Pas certaine de comprendre, mais pour que:

Supposons que le tableau (3*3) ci-dessous représente notre tableau de départ avec les valeurs suivantes :
(A B C)
1 0 1
0 1 1
1 1 1

donne:

Notre tableau final doit alors afficher ceci :
A B A
A B B
A B C
A C A
A C B
A C C
C B A
C B B
C B C
C C A
C C B
C C C

alors quelque chose comme:

Code: Tout sélectionner

function arrangement(&$table) {
  // initialisations
  $lettres='ABCDEFGHIJKLMNOPQRSTUVWXYZ'; // maximum de 26 élements de A à Z
  $lignes=count($table); // nombre de lignes indiquent la largeur des items
  $colonnes=count($table[0]); // nombre de colonnes indiquent le nombre d'éléments
  $resultats=array(); // tableau des résultats
  $travail=array(); // éléments en travail
  $indices=array(); // indices des positions
  // transposer la table
  $arrangements=1;
  for($i=$lignes-1;$i>-1;$i-=1) {
   $indices[$i]=1;
   for($j=0;$j<$colonnes;$j++) {
    if($table[$i][$j]) {
     $travail[$i][]=$j;
    }
   }
   $arrangements*=count($travail[$i]);
   if($i<($lignes-1)) {
    $indices[$i]=$k;
    $k=$indices[$i]*count($travail[$i]);
   }
   else {$k=count($travail[$i]);}
  }
  // generer les résultats
  for($i=0;$i<$arrangements;$i++) {
   $resultats[$i]='';
   $div=$i;
   $mod=0;
   for($j=0;$j<$lignes;$j++) {
    $mod=$div%$indices[$j];
    $div=(int)($div/$indices[$j]);
    $resultats[$i].=$lettres[$travail[$j][$div]];
    $div=$mod;
   }
  }
  // retourner la table
  return $resultats;
}

// EXEMPLE

// données initiales
$TabDepart=array(
  array(1,0,1),
  array(0,1,1),
  array(1,1,1));

// appel de la fonction
$TabFin=arrangement($TabDepart);

// afficher les résultats
for($i=0;$i<count($TabFin);$i++) {
  echo $TabFin[$i],'<br>';
}


Tisha

[unlu]

Bon on va tout reprendre en simplifiant toute l'histoire.

J'ai un premier tableau TabDepart qui contient que des 0 ou des 1, comme par exemple le tableau suivant :

1 0 1
1 0 1
1 1 1

La première colonne de ce tableau va représenter la lettre A, la deuxième la lettre B et la troisième la lettre C.

Ce que je veux obtenir à partir d'une fonction à laquelle on passe en paramètre le tableau ci-dessus, c'est un nouveau tableau comme ci-dessous :

A A A
A A B
A A C
A C A
A C B
A C C
C A A
C A B
C A C
C C A
C C B
C C C

Comment je crée ce tableau final ? Et bien c'est simple je prens mon tableau de départ, 1ère ligne 1ère colonne j'ai un "1" donc j'écris A.
Deuxieme ligne 1ère colonne j'ai un "1" donc j'écris encore A. Troisième ligne 1ère colonne j'ai un "1" donc j'écris encore un A. J'obtiens donc la première ligne de mon tableau final qui est A A A.
Ensuite pour la deuxieme ligne de mon tableau final, 1ère ligne 1ère colonne du tableau de départ j'ai un "1" donc j'écris un A, 1ère ligne deuxieme colonne j'ai un "1" donc j'écris un A. Troisième ligne deuxieme colonne j'ai un "1" donc j'écris B. La deuxieme ligne de mon tableau final est donc A A B.
Troisième ligne de mon tableau final :
1ère ligne 1ère colonne j'ai un "1" donc j'écris un A, 2ème ligne 1ère colonne j'ai un "1" donc j'écris un A, 3ème ligne 3ème colonne j'ai un "1" donc j'écris un C. La troisième ligne de mon tableau final est donc A A C.
Quatrieme ligne de mon tableau final :
1ère ligne 1ère colonne j'ai un "1" donc j'écris un A, 2ème ligne 2ème colonne j'ai un "0", quand on a un "0" on passe à la colonne suivante et on se porte sur la 2ème ligne et 3ème colonne où on a un "1" donc j'écris C, 3ème ligne 1ère colonne j'ai un "1" donc j'écris un A. La quatrième ligne de mon tableau final est donc A C A. etc...

J'éspère avoir été + claire cette fois ci...

[unlu]

Ah j'ai un premier code... de la part de Tisha.
je vais tout de suite vous répondre pour vous dire si c'est bien ce que je voulais...

[unlu]

Et bien Tisha t'es la championne du monde !!!!
C'est bien ce que je voulais et je te remercie du fond de tout mon coeur...

Juste au passage ca t'as pris combien de temps pour résoudre ce problème? Je suis bien curieux parcque j'y est passé plusieurs heures sans pour autant y parvenir...

[unlu]

Bon le code est impeccable cependant j'aimerai comprendre le code, et il y'a des points que je ne comprens pas...

Comme déjà l'argument passé à la fonction : &$table. A quoi sert le &?
Ensuite il y a une ligne où on a $travail[$i][]=$j; peut on référencer une case d'un tableau tout en oubliant un indice ??? Je suis assez perplexe...

Merci pour ces précisions...

[unlu]

Avec mes recherches j'ai réussi à répondre à une de mes questions l'indice d'une case d'un tableau qui n'est pas référencé est automatiquement incrémenté ce que je ne savais pas et qui me posait problème dans la résolution de mon problème !!!!!!!!!!!!!!!

[unlu]

le & dans &$table permet de passer l'argument dans la fonction par référence, dans la mesure où l'on souhaite modifier les valeurs de ce dernier. Je pense que le passage par référence est inutile ai je raison ?

[Tisha]

Comme déjà l'argument passé à la fonction : &$table. A quoi sert le &?

Sans le &, le tableau globale "TabDepart" serait copier dans la variable locale "table". Avec le &, seul la référence mémoire de "TabDepart" est passé à "table". Cela peut économiser de la mémoire et accélérer le fonctionnement dans le cas des tableaux avec beaucoup de données. Aussi, le & implique que tout changement fait à "table" sera en fait une modification à "TabDepart".

Ensuite il y a une ligne où on a $travail[$i][]=$j; peut on référencer une case d'un tableau tout en oubliant un indice ???

C'est tout à fait autorisé, un indice vide indique à php de prendre le prochain indice disponible. Ce qui est obligatoire dans ce cas ci, puisqu'il y a un nombre différent de lettres par position.

Tisha

[Tisha]

le & dans &$table permet de passer l'argument dans la fonction par référence, dans la mesure où l'on souhaite modifier les valeurs de ce dernier. Je pense que le passage par référence est inutile ai je raison ?

c'est à toi de décider, le résultat en sortie sera le même.

Tisha

[unlu]

Félicitations Tisha, merci beaucoup pour tout ce que tu as fait...