Forum d'entraide PHPFrance

Bonjour tout le monde,

Je ne sais pas si il s'agit du bon forum pour ma question, mais j'ai besoin de votre aide !

J'ai un tableau de valeurs, et j'ai besoin de calculer toutes les sommes possibles résultant de l'addition d'un nombre variable des valeurs extraites de ce tableau. Ainsi, je peux avoir besoin des résultats de a + b, comme de a + b + c etc... Je vous sens un peu perdus, je suis pas forcément très clair ! Avec un exemple, ça ira peut-être mieux..

Disons que j'ai un tableau qui contient [3, 4, 5]. Je veux faire une somme a + b + c de toutes les valeurs de ce tableau. Je dois générer un nouveau tableau avec les résultats de :

3 + 3 + 3
3 + 3 + 4
3 + 3 + 5
3 + 4 + 3
3 + 4 + 4
3 + 4 + 5

etc ....

En gardant en tête que je peux avoir besoin des résultats de a + b +c + d +e + f ... (etc ! Jusqu'à 12 variables possibles dans l'addition.)

La syntaxe php ne me pose pas de problèmes, mais il s'agit vraiment plus d'un problème d'algo.. J'ai beau chercher, je ne trouve pas comment structurer ma fonction. Auriez-vous des pistes à me proposer ? Je suis déjà en retard sur ce projet, et je galère pour me sortir de ce calcul... Toute aide serait grandement appréciée !

Merci par avance !!

Si j'ai bien compris, le nombre de termes d'une addition est toujours équivalent au nombre d'éléments dans le tableau source; C'est bien ça?

Désolé si ce n'était pas très clair.

Non, le nombre de termes de l'addition est variable, il est défini par l'utilisateur. Il peut être compris entre 1 (dans ce cas, le tableau de résultat est égal au tableau initial de valeurs) et 12.

J'aimerais générer un tableau contenant les valeurs de toutes les sommes possibles, pour un nombre variable d'éléments.

A titre d'exemple, grâce à la fonction suivante, j'arrive à calculer toutes les sommes d'une addition à 3 termes. Mais j'aimerais que cette fonction soit adaptable en fonction du nombre d'éléments à additionner. Je pense qu'il faut que je transforme ceci en une fonction récursive, mais j'ai un peu de mal...

$epaisseurs = array (3, 4, 5);
getEpaisseurs($epaisseurs);

function getSommes($epaisseurs)
{	
	foreach ($epaisseurs as $ep1)
	{
		foreach ($epaisseurs as $ep2)
		{
			foreach ($epaisseurs as $ep3)
			{
				$res = $ep1 + $ep2 + $ep3;
				$T2[$res] = $res;
			}
		}
	}

	return $T2;
}

Modération: Ce message a été posté par invité avant d'être ré-attribué à son auteur Draxx, suite à sa demande.

Mais attention à problème de charge de calcul, pour 2 termes tu auras normalement 2^2 =4 cas possibles de somme. Pour 4 termes tu en auras 4^4=256 et pour 12 termes tu auras l'horrible nombre de 8916100448256 cas possibles, c'est à dire 12^12.

Quoi qu'il en soit, selon la complexité d'un algorithme, on peut décider de donner la main à PHP pour qu'il génère lui même le programme dont on connait le spécimen redondant.
Cette méthode s'appuie sur le principe d'auto génération de script. Il faut écrire donc un programme qui auto génère un autre programme dont la séquence est connu d'avance mais qui contient des parties redondantes.

Si tu remarque dans ton script, les "foreach" se multiplient selon le nombre de termes à sommer, ainsi que l'opération de somme etc... Donc ton script peut être treaité facilement par la méthode d'auto génération. En résultat, on obtiendra le "VRAI" programme qui va faire la somme.

Voici une première idée sur ce genre de script :
auto_gen_script_somme.php

<pre>
<?php 
// données sources
$termes = array(1,2,3,4);

// création des parties variables du script
$valeurs = implode(",", $termes);
$code_foreach = ""; $code_tirage_termes = ""; $code_tirage_somme = "";
for($i=0; $i<count($termes); $i++){
    $code_foreach .= "foreach(\$termes as \$t$i)\n\r";
    $code_tirage_termes .= "\$t$i,";
    $code_tirage_somme .= "+ \$t$i ";
  }
  
// script global à partir d'un modèle type
$modele = "<?php
\$termes = array($valeurs);
\$i=0;
$code_foreach {
\$tirage[\$i]['termes'] = array($code_tirage_termes);
\$tirage[\$i]['somme'] = 0 $code_tirage_somme;
\$i++;
}
print_r(\$tirage);
?>";

// Ecrire le script dans un fichier PHP
file_put_contents("somme.test.php", $modele);

// Exécuter le script PHP généré
include("somme.test.php");
?>
</pre> 

Ce programme génère un autre programme nommé "somme.test.php" qui nous intéresse et qui, lui, calcule les sommes des différents tirages de termes.

Euh, t'es un peu bourrin sadeq…

Alors, la solution d'optimisation est très simple !
Déjà, on va partir sur un principe de base : la récursivité.
Ensuite, on va réfléchir un peu sur les données. A savoir qu'une sélection de la forme [5;3;3] sera totalement équivalente avec une sélection [3;3;5]. Pour réduire le nombre de calculs, on doit s'assurer qu'il n'y a qu'un seul choix possible pour le tableau. Pour cela on peut exiger que la tableau soit rangé par ordre croissant.

On peut donc commencer à coder (la flemme de proposer l'algorithme) :

/*
 * array $elements : Tableau d'éléments dans lequel piocher.
 * int $nb_el : Nombre d'éléments à piocher.
 * array return : Un tableau de tableau des sommes (il suffit de fusionner les tableaux pour avoir le résultat).
 */
function sommes($elements, $nb_el)
{

  // Cas d'arrêt
  if($nb_el == 0) return;

  // Appel de la suite, récursivité
  $tmp = array();
  $tmp[$i] = sommes($elements, $nb_el-1);

  // Construction du tableau
  $tmp2 = array();
  // Itération sur les éléments à ajouter en tête de tableau
  for($i=0; $i<count($elements); $i++)
  {
    $l = 0;
    // Pour chaque élément on fait l'opération sur le résultat de l'appel suivant, on ne peut ajouter une somme que si l'élément suivant est supérieur ou égal à l'élément courant
    for($j=$i; $j<count($tmp); $j++)
    {
      for($k=0; $k<count($tmp[$j]); $k++)
      {
        // Calcul
        $tmp2[$i][$l++] = $tmp[$j][$k] + $elements[$i];
      }
    }
  }

  return $tmp2;

}