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 15 septembre 2006 à 22:19, par Death83

33 commentaires

0PARTAGES

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 !

Votre nom : Votre e-mail :

Décrivez l'erreur que vous souhaitez porter à notre connaissance :

33 commentaires

Commenter Signaler un problème

titoumimi

Expert éminent

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

titoumimi

Expert éminent

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

)

Death83

Membre éclairé

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

titoumimi

Expert éminent

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

)

Death83

Membre éclairé

Le 15/09/2006 à 23:11

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.

FCYPBA

Membre éprouvé

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

titoumimi

Expert éminent

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

)

titoumimi

Expert éminent

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

Anduriel

Membre expérimenté

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"

FCYPBA

Membre éprouvé

Le 16/09/2006 à 10:25

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 ?

Commenter Signaler un problème