Astuce PHP : Algorithme des combinaisons possibles d'un tableau

Le 2006-09-15 22:19:27, par Death83, Membre éclairé

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?

Discussion forum

33 commentaires

titoumimi
Expert éminent

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

le 15/09/2006 à 23:00
titoumimi
Expert éminent

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 )

le 15/09/2006 à 23:05
Death83
Membre éclairé

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

le 15/09/2006 à 23:07
titoumimi
Expert éminent

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

le 15/09/2006 à 23:09
Death83
Membre éclairé

Envoyé par titoumimi

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.

le 15/09/2006 à 23:11
FCYPBA
Membre éprouvé

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

le 15/09/2006 à 23:22

titoumimi

Expert éminent

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

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
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 )

le 16/09/2006 à 9:49

titoumimi

Expert éminent

et normalement, en remplacant toutes les occurences de

Code :

$tableau_valeurs_possibles[] = $tableau_indices;

par

Code :

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

tu obtiens directement tes combinaisons sans doublons

le 16/09/2006 à 10:09

Anduriel

Membre expérimenté

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 :

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

le 16/09/2006 à 10:10

FCYPBA
Membre éprouvé

Envoyé par 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):

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 ?

le 16/09/2006 à 10:25

Poster une réponse