Discussion :

[Death83]

Bonjour à tous,

je voudrais creer une fonction qui donne toutes les combinaison possible de mots contenu dans un tableau.

Par exemple j'ai:

Tab[0]="a";
Tab[1]="b";
Tab[2]="c";
Tab[3]="d";

Je voudrais pouvoir récupérer :

Res[0]="a b c d";
Res[1]="a b d c";
....

Et ceux pour toutes les combinaisons.

Je n'arrive pas à imaginer un algorithme permettant de faire ca. Avez vous des idées?

[titoumimi]

les lettres peuvent-elles se répéter plusieures fois ?

si c'est le cas, il te "suffit" de faire comme pour un cadenas de vélo :

par exemple, tu as un tableau contenant les valeurs 1, 2, et 3.

tu commence par la combinaison 1 1 1
puis tu augmentes l'indice de ton tableau pour le dernier chiffre jusqu'à arriver à la longueur de ton tableau : 1 1 2 - 1 1 3

une fois que tu en est là, tu décales d'un l'indice du deuxième chiffre, en reinitialisant le 3° : 1 2 1

et là, tu relance ta boucle sur le 3°

ça sent le récursif à plein nez ton histoire

[titoumimi]

au pire, même si les lettres ne peuvent se répéter, il te suffit de faire comme ça, puis de dégager les tableaux contenant des doublons... (pas forcément super propre, mais je voit pas mieux )

[Death83]

Ouais malheuresement je dois éviter les doublons. En plus c'est pour créer une requette dynamiquement :/.

C'est vraiment pas évident, d'autant plus que le nombre d'éléments peut varier.

C'est vraiment tordu pour l'esprit tout ca

[titoumimi]

bah pour les doublons, suffit d'appliquer la deuxième solution (c'est pas JMMPP, mais je m'approche )

[Death83]

bah pour les doublons, suffit d'appliquer la deuxième solution (c'est pas JMMPP, mais je m'approche )

Je vais essayer de faire un truc pour voir mais je sais pas pourquoi je sent que ca va m'énerver lol.

Je vous tient au courant.

[FCYPBA]

Pour dédoublonner un tableau, il y a array_unique() qui fonctionne bien sur des chaines de caractères

Sinon, problème fort sympathique pour l'esprit

Edit :
Toutes les lettres doivent etre utilisé ou bien il peut y en avoir moins ??

Pierre

[titoumimi]

ton problème m'a titillé, du coup je m'y suis collé :

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
<?php
	error_reporting(E_ALL | E_STRICT);
 
 
	function cree_tableau_indices() {
		global $longueur_tableau;
		global $tableau_indices;
 
		for ($i = 0; $i < $longueur_tableau; $i++) {
			array_push($tableau_indices, 0);
		}
	}
 
 
 
	function augmente_indice($position) {
		global $tableau_indices;
		global $index_max;
		global $tableau_valeurs_possibles;
 
 
		if ($tableau_indices[$position] < $index_max) {			// Si l'indice de la position en cours est inférieur à d'indice max 
				$tableau_indices[$position]++;
				$position = $index_max;
				$tableau_valeurs_possibles[] = $tableau_indices;
		} else {
			$tableau_indices[$position] = 0;
			$position--;
		}
		if ($position >= 0) {
			augmente_indice($position);
		}
	}
 
 
 
	$tableau_indices = array();
	$tableau = array('a', 'b', 'c');	
 
	$longueur_tableau = count($tableau);
	$index_max = $longueur_tableau - 1;
 
	cree_tableau_indices();
 
	$nbre_passages = 0;
	$tableau_valeurs_possibles[] = $tableau_indices;
	augmente_indice($index_max);
 
	print_r($tableau_valeurs_possibles);
 
 
?>

à la fin, le $tableau_valeurs_possibles contient toutes les combinaisons d'indice possible (avec répétition dans un même tableau, faudra donc filtrer). si tu veux pus de détails sur le code, n'hésites pas

(pis encore toutes mes excuses à yobenzen à qui j'ai essayé de faire debugger un code qui marchait )

[titoumimi]

et normalement, en remplacant toutes les occurences de

Code :

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

$tableau_valeurs_possibles[] = $tableau_indices;

par

Code :

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

1
2
3
if ($tableau_indices == array_unique($tableau_indices)) {
		$tableau_valeurs_possibles[] = $tableau_indices;
	}

tu obtiens directement tes combinaisons sans doublons

[Anduriel]

Moi aussi il m'a titillé pendant 3/4h hier alors j'ai cherché.
La récurrence c'est plutôt chiant
J'ai fini par trouver un code qui renvoit un tableau avec toutes les possiblités et sans les doublons (code plutot simple):
Edit: manque de possibilités j'y travaille.

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
<?php
$tableau = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm' ,'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z');
echo "Possibilités: ".(count($tableau)*count($tableau));
$tableau_resultat = array();
$x = 0;
for($i = 0; $i<count($tableau); $i++) {
   for($u=0; $u<count($tableau); $u++) {
      $possibilite = $tableau[$i];
      for($y=$u; $x<count($tableau); $y++) {
         if (!isset($tableau[$y])) $y = 0;
         if ($y != $i) $possibilite .= $tableau[$y];
         $x++;
      }
      $tableau_resultats[] = $possibilite;
      $x = 0;
   }
}
echo "<pre>";
print_r($tableau_resultats);
echo "</pres>";
 
?>

@ Titoumini: j'ai testé ton code mais la page ne se lance pas sous EasyPHP ("Impossible d'afficher la page").

[FCYPBA]

Moi aussi il m'a titillé pendant 3/4h hier alors j'ai cherché.
La récurrence c'est plutôt chiant
J'ai fini par trouver un code qui renvoit un tableau avec toutes les possiblités et sans les doublons (code plutot simple):

Je ne voudrais pas faire l'empecheur de tourner en rond de service, mais il manque qqs possibilités. Ton code parcourt le tableau dans l'ordre mais comment mettre un 'b' après un 'c'.

C'est ici que se truve la partie énervante. Je pense que le code titoumimi semble un peu plus complet avec toutes les combinaisons possibles.

Edit : J'ai essayé ton script titoumimi en le complétant d'une partie finale d'affichage, mais j'ai des soucis dès que je dépasse 4 lettres. As tu fait des essais avec plus de 3 lettres ?

[titoumimi]

en testant avec 4, ca marche
maia dès que je passe à 5, ça plante sans plus d'explications

et pourtant, tout est géré dynamiquement, j'arrive vraiment pas à voir le soucis...

[Anduriel]

Pour les doublons c'était pas trop dur à régler mais c'est vrai qu'il manque des possiblités.
En plus ma manière pour compter les possibibilités n'est pas la bonne. D'ailleurs, je trouve pas de fonction factorielle php, ça existe?
Je verrai ça il faut que je trouve

[FCYPBA]

en testant avec 4, ca marche
maia dès que je passe à 5, ça plante sans plus d'explications

et pourtant, tout est géré dynamiquement, j'arrive vraiment pas à voir le soucis...

Pour 3 lettres, 39 passages effectués dans augmente_indice.
Pour 4 lettres, 340 passages effectués !!
Pour 5 lettres, ????

Peut etre que le problème vient de là, ET d'une consomation trop élevée de mémoire.
Il faudrait essayer de se passer de la récursivité

[titoumimi]

le soucis, c'est qu'en se passant de récursivité, je ne voit pas du tout comment gérer une longueur de tableau initial variable ...

[FCYPBA]

le soucis, c'est qu'en se passant de récursivité, je ne voit pas du tout comment gérer une longueur de tableau initial variable ...

Et c'est bien là le problème

J'ai pu aller jusqu'à 1200 valeurs dans le tableau possibilités et 1498 passages dans augmente_indice, aprèc ca plante

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
 
function augmente_indice($position) {
		global $tableau_indices;
		global $index_max;
		global $tableau_valeurs_possibles;
		global $nbre_passages;
 
		++$nbre_passages;
		if ($tableau_indices[$position] < $index_max) {	// Si l'indice de la position en cours est inférieur à d'indice max
			$tableau_indices[$position]++;
			$position = $index_max;
			$tableau_valeurs_possibles[] = $tableau_indices;
			if (sizeof($tableau_valeurs_possibles)>1200) die('1200-'.$nbre_passages);
		}
		else {
			$tableau_indices[$position] = 0;
			$position--;
		}
		if ($position >= 0) {
			augmente_indice($position);
		}
 
	}

[titoumimi]

c'est étonnant tout de même que ça plante comme ça avec 5, pourtant le nombre de solutions possibles (avec doublons) n'est pas si élevé que ça : 5^5 = 3125. ça fait un tout petit peu plus de passages dans ma boucle, mais pas des masses ...

[titoumimi]

sinon, une idée qui me viens là comme ça....

est ce qu'il ne suffirai pas pour un tableau de longueur X de compter de 0 à (X^X - 1) en base X ?

ça permet de récupérer l'ensemble des valeurs d'indice possible, il ne reste plus qu'à dédoublonner.

ça me semble pas mal, on dégage la récursivité, et hop !!!

Edit : pour tout X >= 2 bien entendu

[FCYPBA]

Je suis toujurs bloqué pour essayer de comprendre pourquoi cela plante sans avertissements.

J'ai ajouté une variable qui contient le nombre de fonction augmente_indice imbriqués.

Quand j'ai 5 lettres, et 1217 cases ( juste avant le plantage chez moi ) dans mon tableau de valeur, j'ai plus de 1500 fois la fonction en cours d'éxecution.

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
 
	function augmente_indice($position) {
		global $tableau_indices;
		global $index_max;
		global $tableau_valeurs_possibles;
		global $nbre_passages;
		global $dansfonction;
 
		++$nbre_passages;
		++$dansfonction;
		if ($tableau_indices[$position] < $index_max) {	// Si l'indice de la position en cours est inférieur à d'indice max
			$tableau_indices[$position]++;
			$position = $index_max;
			$tableau_valeurs_possibles[] = $tableau_indices;
			if (sizeof($tableau_valeurs_possibles)>1217) {
				print_r($tableau_indices);
				print_r($tableau_valeurs_possibles);
				die('Taille Tab:'.sizeof($tableau_valeurs_possibles).';Nb.pass:'.$nbre_passages.';Fonction encours:' .$dansfonction .';Posi:'.$position);
			}
 
		}
		else {
			$tableau_indices[$position] = 0;
			$position--;
		}
		if ($position >= 0) {
			augmente_indice($position);
		}
		--$dansfonction;
	}

[FCYPBA]

Encore moi,

Alors je me suis un peu amusé à regardé toute la doc et surtout les fonctions relatives aux tableaux

Ensuite j'ai relu l'énoncé de Death83. Il ne parle pas de la possibilité d'avoir plusieurs fois la même lettre

Donc, j'ai codé ca à la barbare mais cela fonctionne. Comme on ne connait pas l'utilisation finale, pour le moment cela doit suffire si on ne va pas chercher des mots de plus de 10 lettres

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
 
function Factorielle($number){
	$retour = 1;
	if ($number>1) {
		$retour = Factorielle($number-1);
	}
	return $number*$retour;
}
 
 
        $tableau = range('a','f');
	$longueur_tableau = count($tableau);
	$index_max = Factorielle($longueur_tableau);
	$i = 0;
	$Newtableau=array();
	while( $i < $index_max ) {
		do {
			$buffer = $tableau;
			shuffle($buffer);
			$txt_buffer = implode('',$buffer);
		}while(in_array($txt_buffer,$Newtableau));
 
		$Newtableau[$i++] = $txt_buffer;
	}
sort($Newtableau);
print_r($Newtableau);