18041 sujets

Questions générales et questions de débutants

[Résolu] Afficher les combinaisons possibles d'une série de nombres

Bonjour,

Je rencontre quelques difficultés pour afficher des combinaisons de 10 nombres à partir d'un série de 25 nombres.
J'ai bien trouvé un code php qui permet de lister toutes les combinaisons possibles, mais sans restreindre les combinaisons à un maximum de 10 nombres. Voici le code:
$n = 25;
$tableau_elements=array();
for ($nb=1; $nb<=$n; $nb++)
{
	$tableau_elements[] = $nb;
}
$sortie = array();
function liste_combinaison($debut,$tags,$profondeur)
{
	global $sortie;
	if($profondeur == 0)
	{
		array_push($sortie,$debut);
		return;
	}
	$n = count($tags);
	for($i=0;$i<$n;$i++)
	{
		liste_combinaison($debut.$tags[$i]."-",array_slice($tags,$i+1),$profondeur-1);
	}
}
for($i=1;$i<=$n;$i++)
{
	liste_combinaison("-",$tableau_elements,$i);
}
foreach($sortie as $num => $numsympt)
{
	$numsympt= substr($numsympt,0,-1);
	echo''.$numsympt.'<br/>';
}

Le problème c'est que :
- ce code demande trop de mémoire pour 25 éléments et il faut le restreindre à 12 ou 13 éléments.
- je ne parviens pas à limiter les combinaisons à 10 nombres et non à 25.

Pouvez-vous m'aider s'il vous plaît?
Modifié par delphthom (06 Jan 2014 - 16:49)
Bonjour,
Je n'ai pas lu l'intégralité du code que tu as fourni, mais je veux juste te mettre en garde: à mon avis, tu vas galérer pour faire ce que tu veux faire. Si je comprends bien, tu veux afficher toutes les combinaisons de 10 nombres issus d'un tableau de 25 nombres.

Cela fait donc si j'ai bien compris un résultat de 25 puissance 10 possibilités, soit 95367431640625. (car tu vas parcourir une première boucle de 25 nombres, puis une autre de 25, puis une autre de 25... tout ça 10 fois, pour faire tes 10 nombres par combinaison)

Je pense que tu ne pourras jamais afficher autant de combinaisons sans que ça pète au niveau mémoire...
Oui, je galère vraiment!

En fait, il me semble que ça fait quand même pas autant de possibilités. J'ai calculé comme ça:
(25*24*23*22*21*20*19*18*17*16) / (10*9*8*7*5*4*3*2)= 3 268 760. Mais ça fait quand même beaucoup et peut-être effectivement beaucoup trop...

Pour tout dire, il faudrait que je les affiche par paquets de 50 000. Ca réduit le nombre de combinaisons à afficher, mais ça complique un peu plus le code... Pfff c'est pas facile! Smiley ohwell
Modifié par delphthom (06 Jan 2014 - 16:37)
Modérateur
delphthom a écrit :
J'ai calculé comme ça:
(25*24*23*22*21*20*19*18*17*16) / (10*9*8*7*5*4*3*2)= 3 268 760.

Euhh pourquoi la division dans le calcul? Si tu ne crée des combinaisons n'ayant jamais deux fois le même nombre la somme des combinaisons possibles reste: (25*24*23*22*21*20*19*18*17*16) = 11861676288000
Même par paquet de 50'000 ça ferait encore 237 millions de paquets (et des poussières…)

Sinon ton code semble… bizarre, un truc du genre devrait fonctionner, mais pas testé:

function resolve($el, $depth, $comb=array()){
  if ($depth < 1) {
    echo implode('-', $comb)."<br>\n";
    return;
  }
  for ($i=0; $i<count($el); $i--){
     $comb[] = $el[$i];
     $elCopy = $el;
     unset($elCopy[$i]);
     resolve($elCopy, $depth-1, $comb);
  }
}

$n = 25;
$elements=array();
for ($nb=1; $nb<=$n; $nb++) {
	$elements[] = $nb;
}
resolve($elements, 10);
Oui, pardon je n'ai pas été suffisamment précise : l'ordre n'a pas d'importance. Par exemple, les combinaisons 1-2-3 ou 3-2-1 ou 2-3-1, etc...., je les compte comme une seule combinaison. N'étant moi-même pas très douée pour ce type de stats, j'ai recherché avant comment faire le calcul et voici la phrase que j'ai trouvée:
Pour calculer la probabilité de trouver 6 numéros au loto, il suffit de trouver combien il existe de séries non ordonnées de 6 nombres choisis parmi 49. On trouve : (44 x 45 x 46 x 47 x 48 x 49) / (6 x 5 x 4 x 3 x 2)
Du coup, il semble bien que le nombre de combinaisons soit de 3 268 760 en ce qui me concerne.

Mon code semble bizarre mais il fonctionne. D'ailleurs, il n'est pas de moi. Je l'ai trouvé sur phpsources.org (http://www.phpsources.org/scripts317-PHP.htm). Le problème, c'est qu'il consomme trop de mémoire et que je ne peux pas le bloquer à 10 nombres.
Sinon, j'ai testé ton code, mais il ne fonctionne pas. Je vais voir ce qui pourrait bloquer. Merci quand même. Smiley smile
Modifié par delphthom (06 Jan 2014 - 22:27)
En fait, je viens de me rendre compte que ça fait quand même beaucoup plus de combinaisons car car je prend en compte également les combinaisons à 9 nombre, à 8 nombres, etc...

Du coup, je laisse tombé, c'est trop volumineux et trop compliqué pour moi. Tans pis Smiley decu
Modérateur
Ah ok je comprends mieux.
J'avais aussi fait quelques boulettes. J'ai modifié selon. Testé, et approuvé (enfin avec des valeurs plus petites Smiley langue ):


function resolve($el, $depth, $comb=array()){
  if ($depth < 1) {
    echo implode('-', $comb)."<br>\n";
    return;
  }
  $lim = count($el);
  foreach ($el as $i => $num){
     $newComb = $comb;
     $newComb[] = $num;
     unset($el[$i]);
       resolve($el, $depth-1, $newComb);
  }
}

$n = 25;
$elements=array();
for ($nb=1; $nb<=$n; $nb++) {
	$elements[] = $nb;
}
resolve($elements, 10);
Modérateur
delphthom a écrit :
En fait, je viens de me rendre compte que ça fait quand même beaucoup plus de combinaisons car car je prend en compte également les combinaisons à 9 nombre, à 8 nombres, etc...

Du coup, je laisse tombé, c'est trop volumineux et trop compliqué pour moi. Tans pis Smiley decu

ça en fait plus mais pas tant que ça

Quand même pour le sport, avec toutes les combinaisons:


function resolve($el, $depth, $comb=array()){
  if ($depth < 1) {
    echo implode('-', $comb)."<br>\n";
    return;
  }
  echo implode('-', $comb)."<br>\n";
  $lim = count($el);
  foreach ($el as $i => $num){
     $newComb = $comb;
     $newComb[] = $num;
     unset($el[$i]);
     resolve($el, $depth-1, $newComb);
  }
}

$n = 25;
$elements=array();
for ($nb=1; $nb<=$n; $nb++) {
	$elements[] = $nb;
}
resolve($elements, 10);
Juste pour information, le nombre de combinaisons de 10 nombres parmi 25 sans tenir compte de l'ordre et sans répétition est bien choose(10,25) = 25!/10!/(25-10)! = 3268760

ET pour compter le nombre de combinaisons contenant de 1 à 10 nombres parmi 25, il suffit d'ajouter dans la liste des nombres possibles autant de nombres « blancs ». Pour trouver le nombre de combinaisons de 1 à 10 nombres il faut ajouter 9 blancs et on a donc choose(10,34) = 34!/10!/(34-10)! = 131128140 possibilités maintenant.

Pour plus de détails, se référer à des cours de combinatoire et de probabilités/statistiques.
Modifié par QuentinC (07 Jan 2014 - 08:23)
Modérateur
QuentinC a écrit :
Pour trouver le nombre de combinaisons de 1 à 10 nombres il faut ajouter 9 blancs et on a donc choose(10,34) = 34!/10!/(34-10)! = 131128140 possibilités maintenant.

Euh non ça fait trop de possibilités. Il faut calculer en fait choose(10,25) + choose(9,25) + … + choose(1,25). Je ne sais pas si il y a une meilleure méthode de calcul (probablement), mais à l'aide d'excel j'obtiens 7119515 Smiley langue
Mince, je viens d'essayer avec des plus petits nombres et tu as raison. Par contre je ne comprends pas pourquoi ma combine des blancs ne marche pas... il faut que j'aille relire mon cours de maths.
Sujet clos
Aller à