[Tableaux] Algorithme pour les combinaisons

Version imprimable

Voir 40 message(s) de cette discussion en une page

allez la version de la mort qui tue ;)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?php
	error_reporting(E_ALL | E_STRICT);
 
	$long_tabl = 4;
	$nbre_combin = pow($long_tabl, $long_tabl);
 
	$cpt = 0;
 
	for($i=0; $i<$nbre_combin; $i++) {
		$chaine_convertie = base_convert($i, 10, $long_tabl);
		while (strlen($chaine_convertie) < $long_tabl) {
			$chaine_convertie = '0'.$chaine_convertie;
		}
		$tableau_index_possibles[] = str_split($chaine_convertie);
	}
	print_r($tableau_index_possibles);
 
?>

et donc, comme j'utilise base_convert, la longueur max du tableau peut être de 36 ;)

et voi la version dédoublonée :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<?php
	error_reporting(E_ALL | E_STRICT);
 
	$long_tabl = 3;
	$nbre_combin = pow($long_tabl, $long_tabl);
 
	$cpt = 0;
 
	for($i=0; $i<$nbre_combin; $i++) {
		$chaine_convertie = base_convert($i, 10, $long_tabl);
		while (strlen($chaine_convertie) < $long_tabl) {
			$chaine_convertie = '0'.$chaine_convertie;
		}
		$tabl_indice_encours = str_split($chaine_convertie);
 
		if ($tabl_indice_encours == array_unique($tabl_indice_encours)) {
			$tableau_index_possibles[] = $tabl_indice_encours;
		}
	}
	print_r($tableau_index_possibles);
?>

Attention tout de même : il y aura (longueur_tableau ^ longueur_tableau) itérations. 32^32, ça commence à faire beaucoup (à la louche 1.5 .10^48)...

16/09/2006, 14h34
FCYPBA

Comme quoi on pouvait s'en sortir sans recursivité.

Par contre, ta solution ne répond pas au problème qui était les combinaisons de lettres possibles (si 'a' présent une fois alors une seule fois présent dans la solution), mais je pense que ta solution est plus propre que la mienne.

Il reste juste à afficher les résutats:D
16/09/2006, 15h01
titoumimi

exactement, ma solution donne les index du tableau initial à afficher pour avoir le résultat ;)

m'enfin, je ne pense pas que l'affichage pose de soucis à quelqu'un, laissons donc dans l'état ;)

bon, finalement, dans un élan de gentillesse hors du commun, voici le script qui réponds exactement à la question de départ :

Version avec doublons :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<?php
	error_reporting(E_ALL | E_STRICT);
	$mon_tableau = array('a', 'b', 'c');
	$long_tabl = count($mon_tableau);
	$nbre_combin = pow($long_tabl, $long_tabl);
 
	$cpt = 0;
 
	for($i=0; $i<$nbre_combin; $i++) {
		$chaine_convertie = base_convert($i, 10, $long_tabl);
		while (strlen($chaine_convertie) < $long_tabl) {
			$chaine_convertie = '0'.$chaine_convertie;
		}
		$tabl_indice_encours = str_split($chaine_convertie);
 
		$chaine_finale = '';
		foreach ($tabl_indice_encours as $element) {
			$chaine_finale .= $mon_tableau[$element];
		}
		$tableau_index_possibles[] = $chaine_finale;
	}
	print_r($tableau_index_possibles);
?>

Version sans doublons :

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
<?php
	error_reporting(E_ALL | E_STRICT);
	$mon_tableau = array('a', 'b', 'c');
	$long_tabl = count($mon_tableau);
	$nbre_combin = pow($long_tabl, $long_tabl);
 
	$cpt = 0;
 
	for($i=0; $i<$nbre_combin; $i++) {
		$chaine_convertie = base_convert($i, 10, $long_tabl);
		while (strlen($chaine_convertie) < $long_tabl) {
			$chaine_convertie = '0'.$chaine_convertie;
		}
		$tabl_indice_encours = str_split($chaine_convertie);
 
		if ($tabl_indice_encours == array_unique($tabl_indice_encours)) {
			$chaine_finale = '';
			foreach ($tabl_indice_encours as $element) {
				$chaine_finale .= $mon_tableau[$element];
			}
			$tableau_index_possibles[] = $chaine_finale;
		}
	}
	print_r($tableau_index_possibles);
?>

:mrgreen:

16/09/2006, 16h08
Death83

Waou bas dis donc il y'en a qui se sont creusé se matin lol.

Merci beaucoup je vais tester cette dernière version ;).

Juste ca sert à quoi ca:
error_reporting(E_ALL | E_STRICT);
16/09/2006, 16h24
titoumimi

ça sert juste à afficher tout les warnings et autres erreurs. utille en phase de dev seulement, faut le passer à 0 en prod

Solution complémentaire sans le dégagement de doublons):
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 $tabl = array('a', 'b', 'c'); $long_tabl = count($tabl); $tabl_result = $tabl; for($i=1; $i<$long_tabl; $i++) { foreach($tabl as $element1) { foreach($tabl_result as $element2) { $tabl_temp[] = $element1.$element2; } } $tabl_result = $tabl_temp; unset($tabl_temp); } print_r($tabl_result);
Mais comme dans le code précédent, dès qu'on passe à 8 éléments, PHP craque... L'avantage, c'est qu'on ne joue plus avec les index.

il faudrait peut-être l'optimiser en décomposant la longueur du tableau en sommes de petits chiffres, comme ça au lieu de 'multiplier' à chaque fois par le tableau de combinaisons au niveau 1, on pourra passer au niveau 2 ou 3, ça devrait faire gagner des pèpètes ;)

Allez, version optimisée sans doublons :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 $tabl = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'); $long_tabl = count($tabl); $tabl_result = $tabl; for($i=1; $i<$long_tabl; $i++) { foreach($tabl as $element1) { foreach($tabl_result as $element2) { if (strpbrk($element1, $element2) == false) { $tabl_temp[] = $element1.$element2; } } } $tabl_result = $tabl_temp; unset($tabl_temp); } print_r($tabl_result);
ça m'a permis de vachement réduite le nombre d'itérations (986400 'seulement' pour un tableau initial de longueur 9). Attention tout de même, le dédoublonnage à l'aide de la fonction strpbrk suppose que le tableau ne contient que des chaines uniques de longueur 1.

16/12/2006, 21h04
r.mnr

Tu peux crée un dictionnaire (un arbre)
par exemple sabot, sabine, ca.
Tu vas sur la lettre S, tu trouves un pointeur vers un arbre qui contient les deuxièmes lettres
par exemple tu trouves sa, sabot, sabine.
un flag te previens que tu peux pointer vers une troisieme lettre mais que tu as également une feuille.
et ainsi de suite.
La recherche s'arrête lorsqu'il n'y a plus depointeurs vers un autre arbre.
Chaque arbre est un tableau, avec, les lettres, les pointeurs vers le tableau suivant et les flags.
Ce n'est pas très simple sans schéma.
BA
17/09/2007, 16h58
morck

Pour éviter les doublons, une astuce peut être d'associer à chaque élément constitutif un nombre premier(depuis une bibliothèque) et d'indexer une combinaison obtenue avec le produit de ses éléments. Ainsi pas de doublons. ex : 1 => a, 2 => b, 3 => c, 5 => d, 7 => e et 11 => f...
abc = 6 = bca <> bcd, aef, cbe, aaa, aaaa, ... et ça marche queque soit le nombre d'éléments constitutifs et d'éléments des combinaisons.

Meme si c'est un peu tard, je vous soumets mon code que je viens de faire,
n'ayant pas trouvé exactement ce que je voulais.

Ps: le code ci-dessous fait exactement ce que je voulais :
trouver toutes les combinaisons possibles de valeurs
entre différents tableaux.

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
<?php
/* 
 *  This is the XXX Project Licence
 * do What The Fuck you want to Public License
 * 
 * Version 1.0, March 2000
 * Copyright (C) 2000 Banlu Kemiyatorn (]d).
 * 136 Nives 7 Jangwattana 14 Laksi Bangkok
 * Everyone is permitted to copy and distribute verbatim copies
 * of this license document, but changing it is not allowed.
 * 
 * Ok, the purpose of this license is simple
 * and you just
 * 
 * DO WHAT THE FUCK YOU WANT TO.
 * 
 */
 
/**
 * Ling_Function_ArrayMixer.php
 * 
 * @author Ling
 * 12 déc. 2009 16:52:36
 * 
 */
 
class Ling_Function_ArrayMixer
{
    protected $result;
    protected $popNext;
    protected $matrix;
    protected $newArray;
    protected $oldArray;
 
    public function __construct()
    {
        $this->result  = array();
        $this->popNext = false;
        $this->matrix  = array();
        $this->newArray  = array();
        $this->oldArray  = array();
    }
 
    public function append(array $array)
    {
        $this->matrix[] = $array;
    }
 
    public function makeTree()
    {
 
        $lastArray = array_pop($this->matrix);
        if(count($this->matrix) > 0)
        {
            foreach(end($this->matrix) as $k => $v)
            {
                $this->newArray[$v] = $lastArray;
            }
 
            while(count($this->matrix) > 1)
            {
                $lastArray = array_pop($this->matrix);
                $this->oldArray = $this->newArray;
                $this->newArray = array();
                foreach(end($this->matrix) as $k => $v)
                {
                    $this->newArray[$v] = $this->oldArray;
                }
            }
        }
        else
        {
            $this->result = $lastArray;
        }
 
    }
 
    public function ListageArray($tb, $todisplay=array())
    {
        foreach($cit = new CachingIterator(new ArrayIterator($tb)) as $key => $value)
        {
            if(is_array($value))
            {
                if($this->popNext === true)
                {
                    array_pop($todisplay);
                    $this->popNext = false;
                }
                $todisplay[] = $key;
                self::ListageArray($value, $todisplay);
            }
            else
            {
                $prefix = implode("_",$todisplay) . "_";
                $this->result[] = $prefix . $value;
                if(!$cit->hasNext())
                {
                    $this->popNext = true;
                }
            }
        }
    }
 
    public function proceed()
    {
        $this->makeTree();
        $this->ListageArray($this->newArray);
    }
 
    public function result()
    {
        return $this->result;
    }
 
}
 
//$t1 = array('a','b','c');
//$t2 = array('m1','m2','m3','haha','oups');
//$t3 = array('ok','ko');
//$t4 = array('poule','merci','yoma');
//
//$x = new Ling_Function_ArrayMixer();
//$x->append($t1);
//$x->append($t2);
//$x->append($t3);
//$x->append($t4);
//$x->proceed();
//a($x->result());

Si qqn a une solution plus élégante je suis preneur.
:aie:

modification de cette fonction

j'ai essayé de modifier cette fonction pour rendre récursive mais le probléme est que j'ai des duplications des champs:
voici le code

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
 
function combinaison($mc,$m)
 { 
      $tableau = array();
      $x=0;
 
	  while($m>0)
	  {
       for($i=0;$i<=$m;$i++) 
	   {
	    for($u=0;$u<=$m;$u++)
	     { $possible =$mc[$i];
		   for($y=$u;$x<$m;$y++)
		    {
		      if (!isset($mc[$y])) $y = 0;
                 if ($y != $i) $possible .= '&nbsp;'.$mc[$y];
			  $x++;
             }
 
 
           $tableau[].= $possible;
		   $x =0; 
		   }
	    }
	   $m=$m-1;
	   self::combinaison($mc,$m);
      }
 
  return $tableau;
 
 }

y'a t-il quelqu'un peut m'aider à améliorer ce code pour que ne puisse pas avoir de duplication
merci

09/08/2010, 15h31
Onimaru

Réponse

Salut à tous,
Il y une réponse à ce problème dans cette discutions :

http://www.developpez.net/forums/d96...ons-possibles/

Voir 40 message(s) de cette discussion en une page