Discussion :

[spawns]

Salut à tous,
je suis entrain de me triturer le cerveau pour connaitre le nombre de combinaisons possibles
sachant que :
J'ai 4 lettres = A B C D
- une longueur de 1 à 4 lettres (j'ai donc 4 longueurs possibles X, XX, XXX, XXXX)
- avec impossibilité d'utiliser 2 fois la même lettre pour 1 combinaison (pas de AA, BBBB...)
- Et sachant que l'ordre n'a pas d'importance et compte pour 1 ( ABCD = DBAC = DCBA ...)

je dois donc pouvoir sortir 15 combinaisons
A
B
C
D
--------
A+B
A+C
A+D
B+C
B+D
D+C
--------
A+B+C
A+B+D
A+C+D
C+B+D
--------
A+B+C+D

Donc la questions
comment faire cela en php ? existe t'il des fonctions générant cela ?

Merci d'avance de votre aide
Cdt

[sabotage]

C'est des maths ça, pas du PHP.
Ton nombre de combinaison de 3 éléments par exemple c'est 4! / (4 - 3)! 3! = 4

[Loralina]

Bonjour,
Vous les avez vos combinaisons, il n'y a plus qu'à les mettre dans un array.

Vous dîtes "je suis entrain de me triturer le cerveau pour connaitre le nombre de combinaisons possibles", puis "je dois donc pouvoir sortir 15 combinaisons".
S'agit-il d'avoir la formule qui donne le nombre de combinaisons ou d'en obtenir la liste ?

Pour un script général qui donne la liste, j'ai fait un brouillon en vitesse, à optimiser (et à vérifier, quoique la sortie paraît bonne) :

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
18
19
20
21
22
23
24
<?php
function combinaisons($ar_st_cara,$nb_longComb)
	{
	if(count($ar_st_cara)<$nb_longComb)
		{
		return [];
		}
	if($nb_longComb===1)
		{
		return $ar_st_cara;
		}
	$st_cara=array_shift($ar_st_cara); //pas le plus optimisé, "pop" est préférable
	$ar_st_comb=[];
	foreach(combinaisons($ar_st_cara,$nb_longComb-1) as $st_comb)
		{
		$ar_st_comb[]=$st_cara.$st_comb;
		}
	return array_merge($ar_st_comb,combinaisons($ar_st_cara,$nb_longComb));
	}
foreach($ar_st_cara=['A','B','C','D'] as $i=>$st_cara)
	{
	var_dump(combinaisons($ar_st_cara,$i+1));
	}
?>

[badaze]

Pour avoir le nombre de combinaisons (à tester car je me suis contenté de peu).

Code php :

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
18
19
20
21
22
23
 
<?php
function fact($n) {
 if ($n == 0) return 1;
 return $n * fact($n-1);
}
function comb($n,$k) {
 return fact($n) / (fact($k) * fact($n-$k));
}
function sommeComb($n,$k) {
 $resultat = 0;
 for ($i=1;$i<=$k;$i++) {
  $resultat = $resultat + comb($n,$i);
 }
 return $resultat;
}
print fact(8);
print "<br/>";
print fact(0);
print "<br/>";
print comb(4,1) + comb(4,2) + comb(4,3) + comb(4,4);
print "<br/>";
print sommeComb(4,4);

[CosmoKnacki]

Une méthode rigolote consiste à représenter chaque combinaison par un nombre entier allant de 1 jusqu'à la dernière combinaison. Pour ce faire, on associe à chaque lettre un bit. Par exemple A = 0001 = 1, B = 0010 = 2, AB = 0011 = 3, C = 0100 = 4, AC = 0101 = 5, ..., ABCD = 1111 = 15. Donc ensuite il suffit de faire une boucle allant de 1 à 15 et de tester chaque bit pour savoir quelles sont les lettres présentes pour un entier donné.

Précision: la somme des combinaisons pour n éléments est 2 puissance n. (Si on enlève l'élément vide, ça fait 2^n - 1)

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
$letters = ['A', 'B', 'C', 'D', 'E'];
 
function getCombination($letters) {
    $numberOfCombinations = 1 << count($letters);
    for ($i = 1; $i < $numberOfCombinations; $i++) {
        $combination = [];
        foreach($letters as $k => $letter) {
            if ( $i & 1 << $k )
                $combination[] = $letter;
        }  
        yield $combination;
    }
}
 
foreach (getCombination($letters) as $combination) {
    echo implode(' ', $combination), PHP_EOL;
}

[spawns]

Bonjour,
Vous les avez vos combinaisons, il n'y a plus qu'à les mettre dans un array.

Vous dîtes "je suis entrain de me triturer le cerveau pour connaitre le nombre de combinaisons possibles", puis "je dois donc pouvoir sortir 15 combinaisons".
S'agit-il d'avoir la formule qui donne le nombre de combinaisons ou d'en obtenir la liste ?

Pour un script général qui donne la liste, j'ai fait un brouillon en vitesse, à optimiser (et à vérifier, quoique la sortie paraît bonne) :

oui c'est exactement ce que je cherchais a faire.

Merci

[badaze]

Avec possibilité d'avoir les combinaisons avec ou sans notion d'ordre.

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
<?php
function _permutations(&$listeElements,$profondeur,$niveau,$arrComb,&$retour,&$arrCtl,$notionOrdre,$str="") 
{
 if ($niveau < ($profondeur-1)) 
 {
  for($l=0;$l<count($listeElements);$l++) 
  {
   $ll = $listeElements[$l];
   if (!in_array($ll,$arrComb)) 
   {
    $arrComb[$niveau] = $ll;
    $niveau2          = $niveau;
    $sep              = $niveau == 0 ? '' : '|';
    _permutations($listeElements,$profondeur,++$niveau2,$arrComb,$retour,$arrCtl,$notionOrdre,$str.$sep.$ll);
   }
   unset($arrComb[$niveau]);     
  } 
    } 
 else 
 {
  for($k1=0;$k1<count($listeElements);$k1++) 
  {
   $kk = $listeElements[$k1];
   if (!in_array($kk,$arrComb)) 
   {
    $uneLigne = $str == '' ? $kk : $str.'|'.$kk;    
    $elem     = explode('|',$uneLigne);
    if (!$notionOrdre) 
    {
     asort($elem);
     $uneLigne = implode('|',$elem);
    }
    if (!in_array($uneLigne,$arrCtl)) 
    {
     $arrCtl[] = $uneLigne;
     $retour[] = $elem;
    }
   }
  }
 }
} // function _permutations
function permutations($listeElements,$profondeur,$notionOrdre=true) 
{
 $arrComb = array();
 $retour  = array();
 $arrCtl  = array();
 _permutations($listeElements,$profondeur,0,$arrComb,$retour,$arrCtl,$notionOrdre);
 return $retour;
} // function permutations
$a = array("A","B","C","D");
print "Sans notion d'ordre :<br/>";
for($b=1;$b<=4;$b++) {
 foreach(permutations($a,$b,false) as $key => $subarray) {
  foreach($subarray as $key2 => $value) {
   print "$value - ";
  }
  print "<br/>";
 }
}
print "<br/>";
print "Avec notion d'ordre :<br/>";
for($b=1;$b<=4;$b++) {
 foreach(permutations($a,$b) as $key => $subarray) {
  foreach($subarray as $key2 => $value) {
   print "$value - ";
  }
  print "<br/>";
 }
}

Donne :

[Loralina]

Bonjour,
CosmoKnacki, c'est la grande classe.
Astucieux le test du if, il faut avoir l'habitude de ces opérateurs pour y penser.
Au passage, pour la puissance, on a aussi l'opérateur **.

[CosmoKnacki]

Merci, c'est gentil.

L'idée est de trouver une représentation qui soit la plus pratique/économique possible. Donc en suivant ce fil on peut tester si au niveau bits (avec leurs contraintes et avantages) une idée émerge. Rien de sorcier, ça aboutit à quelque chose ou à rien.

En ce qui concerne le calcul de puissance, le décalage de bit étant une instruction de base du processeur, dans ce cas précis (puissances de 2), mieux vaut l'utiliser, plutôt qu'une fonction plus générale (x**y) qui doit prendre en charge des données plus hétérogènes. Cela dit, pour un langage interprété comme le php, la différence doit être assez minime.

Maintenant le défaut de ce script est qu'il ne renvoie pas les combinaisons dans l'ordre auquel on pourrait s'attendre, mais rien n'a été explicitement précisé à ce sujet.