IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Astuce PHP : Algorithme des combinaisons possibles d'un tableau

Le , par Death83

0PARTAGES

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

Une erreur dans cette actualité ? Signalez-nous-la !

Avatar de titoumimi
Expert éminent https://www.developpez.com
Le 15/09/2006 à 23:00
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
0  0 
Avatar de titoumimi
Expert éminent https://www.developpez.com
Le 15/09/2006 à 23:05
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 )
0  0 
Avatar de Death83
Membre éclairé https://www.developpez.com
Le 15/09/2006 à 23:07
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
0  0 
Avatar de titoumimi
Expert éminent https://www.developpez.com
Le 15/09/2006 à 23:09
bah pour les doublons, suffit d'appliquer la deuxième solution (c'est pas JMMPP, mais je m'approche )
0  0 
Avatar de Death83
Membre éclairé https://www.developpez.com
Le 15/09/2006 à 23:11
Citation 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.
0  0 
Avatar de FCYPBA
Membre éprouvé https://www.developpez.com
Le 15/09/2006 à 23:22
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
0  0 
Avatar de titoumimi
Expert éminent https://www.developpez.com
Le 16/09/2006 à 9:49
ton problème m'a titillé, du coup je m'y suis collé :

Code : Sélectionner tout
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 )
0  0 
Avatar de titoumimi
Expert éminent https://www.developpez.com
Le 16/09/2006 à 10:09
et normalement, en remplacant toutes les occurences de

Code : Sélectionner tout
$tableau_valeurs_possibles[] = $tableau_indices;
par

Code : Sélectionner tout
1
2
3
if ($tableau_indices == array_unique($tableau_indices)) {
		$tableau_valeurs_possibles[] = $tableau_indices;
	}
tu obtiens directement tes combinaisons sans doublons
0  0 
Avatar de Anduriel
Membre expérimenté https://www.developpez.com
Le 16/09/2006 à 10:10
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
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".
0  0 
Avatar de FCYPBA
Membre éprouvé https://www.developpez.com
Le 16/09/2006 à 10:25
Citation 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 ?
0  0