Toutes les combinaisons possibles d'un tableau

[absot]

Bonjour, je suis en train de créer une fonction qui reçoit en paramètre un tableau et retourne toutes les combinaisons possibles de ce tableau.

Par exemple, si on reçoit le tableau suivant:

Code :

1
2
 
$tableau = array("a", "b");

Je voudrais faire en sorte de créer toutes les combinaisons possibles avec toutes les tailles possibles.

Avec ce tableau, ca doit retourner:

a
b
aa
ab
ba
bb

Voilà actuellement où j'en suis:

Code :

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
 
// longueur actuelle du mot
$longueur = 1;
// longueur maximum des mots
$longueurMax = 3;
// 
$i = 0;
// mot actuel
$currentWord = "";
$tabExemple = array("a", "b");
// nombre de caracteres dans le tableau
$nbrTab = count($tabExemple)-1;
// nombre de mots total
$nbrTotal = 0;
 
while($longueur <= $longueurMax)
{
	$nbrTotal = $nbrTotal + parcourDictionnaire($tabExemple, $currentWord);
 
	if($i <= $nbrTab)
	{
		$currentWord = $currentWord . $tabExemple[$i];
		$i++;
	}else
	{
		$i = 0;
	}
	$longueur++;
}
 
echo "Nombre d'entree dans le tableau: " . $nbrTab . "<br/>";
echo "Nombre total de mots: " . $nbrTotal;
 
function parcourDictionnaire($tabCaractere, $motCourant)
{
	$nbr = 0;
	foreach($tabCaractere as $caractere)
	{
		echo $motCourant . $caractere . "<br/>";
		$nbr++;
	}
	return $nbr;
}

Malheureusement, cela me renvoit:

a
b
aa
ab
aba
abb

Et je ne sais pas trop malheureusement ce qui ne va pas. :/

[Climoo]

J'avoue que je n'ai pas compris grand chose à ta fonction... A vrai dire, je ne sais pas quel algorithme tu as voulu utiliser derrière. Est ce que tu as essayé de dérouler ton exemple sur papier avec ta fonction ?

Je me permet de te proposer une solution qui a l'air de fonctionner correctement. C'est une fonction récursive, j'espère que tu n'as rien contre, mais dans ton cas, c'est ce qui m'est venu en premier. Essaie de bien comprendre comment elle fonctionne et ne de pas la reprendre bêtement...

Code :

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
 
<?php
/**
 * Retourne tous les combinaisons des éléments de $tab 
 * de taille $taille ou inférieure (de taille supérieure ou égale à 1)
 * @param array $tab tableau des éléments de base
 * @param int taille maximale des combinaisons résultantes
 * @return array toutes les combinaisons
 */
function combinaisons(array $tab, $taille)
{
	// Cas de base : pour une taille de 1, on retourne simplement le tableau
	if ($taille == 1) {
		return $tab;
	}
	else {
		// Cas général :
		// Tableau de résultats final
		$result = array(); 
		// Calcul des combinaisons pour la taille inférieure (appel récursif)
		$combinaisons = combinaisons($tab, $taille - 1);
		// Création des nouvelles combinaisons à partir de celle de taille inférieure: 
		// On ajoute chaque caractère de départ devant chacune des combinaisons trouvées
		foreach($tab as $caractere) {
			foreach($combinaisons as $combinaison) {
				$result[] = $caractere . $combinaison;
			}
		}
		// Le résultat est aussi bien les combinaisons de taille inférieure que celle générées
		// On met donc les deux ensemble
		$result = array_merge($result, $combinaisons);
		return $result;
	}
}
 
echo 'test 1 array("a", "b"), taille 2';
var_dump(combinaisons(array("a", "b"), 2));
 
echo 'test 2 array("a", "b"), taille 3';
var_dump(combinaisons(array("a", "b"), 3));
 
echo 'test 3 array("a", "b", "c"), taille 3';
var_dump(combinaisons(array("a", "b", "c"), 3));
?>

Attention quand même, c'est le genre de fonction qui va très vite prendre du temps (la sortie est de taille exponentielle, pour un tableau de taille 2, si tu veux toutes les combinaisons de taille inférieure ou égale à n, tu vas avoir dans les 2^(n+1) résultats...)

[EDIT] Petite erreur sur la complexité, c'est pas 2^(n+1), c'est bien plus que ça...

[absot]

J'avoue ne pas tout comprendre

Pourquoi si j'utilise un tableau avec un nombre de caractères supérieur à , ca ne veut pas fonctionner, ca ne charge pas la page?

J'avais essayé pour voir ce que ca donnait sur papier mais je bloquait lorsqu'il s'agit de la combinaison à 2 caractères et de tester avec tout les autres puis de prendre le caractère supérieur dans le tableau..

[Climoo]

Supérieur à combien ? On dirait qu'il manque un chiffre ^^.

Je vais essayer de t'expliquer le principe de ma fonction...
On va partir d'un cas simple avec le tableau (a, b).

Si je veux toutes les combinaisons de taille 1, facile, c'est simplement le tableau de départ (a, b). Ca constitue le cas de base de ma récursivité.

Si je veux toutes les combinaisons de taille 2 ou inférieure, je recherche d'abord toutes celles de taille 1. Ok, je les ai (appel récursif). Comment constituer ceux de taille 2 ? Hé bien en ajoutant chaque caractère du tableau de départ, aux combinaisons de taille 1.
Clairement, j'ajoute 'a' :
devant 'a' (combinaison de taille inférieure) => 'aa'
devant 'b' (combinaison de taille inférieure) => 'ab'
Et j'ajoute 'b' :
devant 'a' (combinaison de taille inférieure) => 'ba'
devant 'b' (combinaison de taille inférieure) => 'bb'
Ce qui me donne 4 nouvelles combinaisons.


Par contre à partir de la taille 3, on a un petit soucis (mais qui peut se corriger facilement). Certains éléments sont en double comme 'aa'. Déroule avec la taille 3 et tu comprendras.
J'avais laissé ce bug exprès pour voir si tu suivais (non en fait je viens de m'en rendre compte^^). C'est vraiment pas dur à corriger si tu as pigé le principe. Je ne met donc pas le code définitif, à toi de le faire...