Discussion :

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

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
 
// 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 :

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
 
<?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...

[thefutureisnow]

Bonjour,

Je me permet de poser ma question sur ce topic car mon problème ressemble beaucoup à celui exposé plus haut, à la différence que mon tableau en entrée est un tableau de chiffres, dont je voudrais exporter toutes les combinaisons de multiplications possibles :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

array(1, 2);

Je souhaiterais avoir ces résultats :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
1
2
1*2

Autre exemple pour ce tableau :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

array(1, 2, 3);

ces résultats :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
1
2
3
1*2
1*3
2*3

Auriez vous éventuellement un algo utilisable ?

Merci !

[Climoo]

Je pense que tu peux adapter l'algo que j'avais proposé plus haut pour avoir ce que tu veux.
Indice : quand on regarde, on remarque que le nombre de gauche est toujours strictement plus petit que le nombre de droite... Un petit if bien placé ferait-il l'affaire ?
Hésite pas à remettre une réponse si tu trouves pas, ou si ce que je dis ne tient pas finalement...