Discussion :

[marsupio49]

Bonjour à tous,
Je ne suis pas sur de poster au bon endroit, et pour cela, accepter mes excuses.

J'ai un problème d'ordre mathématique en PHP.
J'aimerais réussir à connaître tout les arrangements possibles composés de :
- A (10 fois)
- B ( 6 fois)
- C ( 5 fois)

Exemple :

Code :

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

A - A - B - C - C -B - A - C - B -C -A -B - A - A - C - B - B - A - A - A - A

Cette série est bien composée de 10 fois la lettre A, de 6 fois la lettre B et de 5 fois la lettre C.

Je sais que en mathématique si je voulais tout les arrangements de (A,B,C), il suffit de faire :
E=3! soit 6 arrangements possibles,
donc :

Code :

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

abc,acb,bca,bac,cab,cba

Seulement moi je dois voir apparaître 10 fois la lettre A , 6 fois la lettre B et 5 fois la lettre C. Et je ne vois pas du tout comment faire .
Je me demande donc si il y une possibilité de connaître tout les arrangements possible.

Je voudrais par la suite pouvoir intégrer chaque arrangement dans un tableau à deux dimensions en PHP.

Je vous remercie d'avance pour la moindre informations que vous pourriez me fournir.

Amicalement Marsupio,

[marsupio49]

Bonjour,

Pour ce que ça intéresse, ou pour facilité d'éventuel futur recherche, j'ai trouver le moyen de calculer le nombre de possibilités.
Enfait cela fait partie des permutation avec répétition d'objet discernable

Ce qui fait dans mon cas :

Code :

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

1
2
3
4
5
 
n  = 21  soit (10+6+5)
n1 = 10
n2 =  6
n3 =  5

ce qui donne :

Code :

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

1
2
 
(n!)/(n1!n2!n3) = 162 954 792 possibilités.

j'ai trouvé la réponse grâce à un forum de mathématique. http://forums.futura-sciences.com/


Il me reste donc à créer un programme en PHP qui me sortira toutes les solutions (ça va pas être facile ).
Je ne met donc pas ce post en résolu, car je m'en servirais si j'ai d'éventuel soucis dans ma programmation.

Amicalement Marsupio,

[marsupio49]

Re bonjour tout le monde.

J'esper que je ne vais pas me faire taper dessus pour mes posts répétés

En fait je repost car j'ai finis le programme pour avoir toutes les combinaisons.

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
 
<?PHP
$TableauCombinaison = array();
$TableauValeur = array(1 => "a", 2 => "a", 3 => "a", 4 => "a", 5 => "a" ,6 => "a" ,7 =>"a" , 8 => "a" , 9 => "a" , 10 =>"a", 11 =>"b" ,12 =>"b" ,13 =>"b" ,14 =>"b" ,15 =>"b" ,16 =>"b", 17 => "c" , 18 => "c" ,19 => "c", 20  => "c" c, 21 => "c");
 
 
while(count($TableauCombinaison) <= 162 954 791){//tant qu'on a pas trouver toutes les combinaisons on continu à chercher.
    shuffle($TableauValeur);//mélange aléatoirement les valeurs du tableau
 
    if(!in_array($TableauValeur, $TableauCombinaison)){// si la combinaison n'est pas encore sortie on l'enregistre
        array_push($TableauCombinaison, $TableauValeur);
    }
 
 
}
?>

Le code fonctionne, je l'ai testé sur des combinaisons plus petite. Le gros hic c'est que pour la combinaison de 10 fois "a", 6 fois "b" et 5 fois "c," j'ai des petits soucis.
Je m'explique, enfait si je met que je veux 1000 combinaisons de ce type ça va très vite. mais plus j'augmente et plus ça met longtemps.
Le temps n'est enfait pas du tout proportionnelle au nombre de combinaisons voulu.

Cela vient du faite qu'il doit à chaque fois compter plus de valeur dans le tableau pour voir si il continue la boucle et du fait qu'il doit à chaque fois vérifier entre de plus en plus de combinaisons pour savoir si la nouvelle a déjà été tirée.

exemple :

Code :

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

1
2
3
4
 
Pour 10000 combinaisons, je les obtiens toutes en 67 secondes, soit : 67/10000 = 0,0067 secondes pour une combinaison.
 
Pour 5000 combinaisons,  je les obtiens toutes en 14 secondes, soit : 14/5000 = 0,0028 secondes pour une combinaison.

J'imagine même pas le temps que cela pourrait mettre pour avoir les 162.954.972 combinaisons

N'aurais t'il pas des moyens pour diminuer ce temps de recherche à quelque jours plutôt qu'a quelques années :s

Amicalement Marsupio,

[etaty]

Ton problème vient de ton algorithme :
tu cherche à trouver toutes les combinaisons possible d'un dé
par à jeter de dé
(code : shuffle($TableauValeur);//mélange aléatoirement les valeurs du tableau)
ce qui n'est pas du tout le meilleur chemin pour y arriver !!!
(qui te dit que tu ne va pas sortir 5000 fois la valeur "5" du dé avant d'avoir enfin ta valeur "6" ?
(d'où le temps de calcul qui varie comme tu l'a expliqué plus haut !)

Maintenant la vrai solution (plus simple et plus rapide) est de passer par un comptage :
A->0
B->1
C->3

tu compte en trinaire

Donc tu compte de 0 à jusqu'à 333 333 333 333 333 333 333 (21 fois la valeur 3)

Puis dans un second temps tu ne sélectionne que les combinaisons qui n'ont que 5 fois le chiffre 3 et ainsi de suite

[marsupio49]

Je suis totalement d'accord avec toi pour le faite que rien ne me prouve que la même combinaison ne va pas tomber 5000 fois avant d'en essayer une nouvelle.

Mais j'ai pas très bien compris ta solution

moi je veux une combinaison de type :

Code :

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

 A - A - B - C - C -B - A - C - B -C -A -B - A - A - C - B - B - A - A - A - A

donc on remplace la lettre A par 0, B par 1 et C par 3.

Après je fait une boucle de 0 a 333 333 333 333 333 333 333 ?? (21 fois la valeur 3) => et la je ne comprend pas bien pourquoi 21 fois la valeur 3, ce que ça apporte etc ^^'. (si, si j'ai fait des recherches sur google et lu l'article du wiki que tu m'as donné)

Ensuite dans cette boucle il se passe quoi, la je ne comprend pas? Enfait j'ai l'impression que depuis le mot trinaire tout mon cerveau c'est embrouillé

Merci pour tes informations,

Amicalement marsupio,

[etaty]

tu cherche bien une combinaison de 21 lettres ?
donc il faut compter de 0 à "21" fois la valeur 3
A partir de là on aura tout les combinaisons possibles

Sauf que ensuite on ne veut garder que les combinaison avec 10 'A' , 6 'B' et 5 'C' donc on va devoir faire les tests pour y arriver !


pour ce qui est du comptage en trinaire c'est comme si tu comptait en binaire, en décimal, ou hexadécimal ...

[etaty]

voici le code un peu broullons certe

mais 80 000 résultat en 30s tout de même

astuce :
je commence pas à compte à partir de 0 (ou 21 A), mais de la plus petite valeur valide connu :
10A 6B 5C

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
53
54
	$TableauCombinaison = array();
	// a -> 0
	// b-> 1
	// c-> 2
	$TableauValeur = array(1 => "a", 2 => "a", 3 => "a", 4 => "a", 5 => "a" ,6 => "a" ,7 =>"a" , 8 => "a" , 9 => "a" , 10 =>"a", 11 =>"b" ,12 =>"b" ,13 =>"b" ,14 =>"b" ,15 =>"b" ,16 =>"b", 17 => "c" , 18 => "c" ,19 => "c", 20  => "c", 21 => "c");
 
	function incrementer($TableauValeur ,$position)
	{
		if($TableauValeur[$position] == 'a')
		{
			$TableauValeur[$position] = 'b';
			$resultat= $TableauValeur;
		}
		elseif($TableauValeur[$position] == 'b')
		{	
			$TableauValeur[$position] = 'c';
			$resultat= $TableauValeur;
		}
		else
		{
			$TableauValeur[$position] = 'a';
			$position--;
			$resultat= incrementer($TableauValeur,$position);
		}
 
		return $resultat;
	}
 
 
	function valider_resultat($resultat)
	{
		$nb_valeurs = array_count_values($resultat);
		if($nb_valeurs['a'] == 10 && $nb_valeurs['b'] == 6)
			return true;
		else
			return false;
	}
 
 
	echo '<pre>'.print_r($TableauValeur, true).'</pre>';
	$i=1;
	while($TableauValeur[1] != 'c')
	{	
		$position=21;
 
		$TableauValeur = incrementer($TableauValeur,$position);
 
		if(valider_resultat($TableauValeur))
		{
			echo 'resultat valide n° '.$i++;
			$Tableau_resultat[] = valider_resultat($TableauValeur);
			echo '<pre>resultat :'.print_r($TableauValeur, true).'</pre>';
		}
	}

[marsupio49]

Là je commence a comprendre, mais si je ne me trompe ton code ne trouvera pas toutes les combinaisons possibles. Car la condition de sortie de ta boucle est :

Code :

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

1
2
 
$TableauValeur[1] != 'c'

donc dés que la lettre C se retrouve en première position, ton script s'arrête.
Hors il peut y'avoir plusieurs combinaison qui commence par la lettre C.

je l'ai testé avec des valeur plus petites, tel que 2 fois la lettre 'A', 1 fois la lettre 'B' et 1 fois la lettre 'C'. Il y a 12 configurations différentes (dont 3 commençant par la lettre 'C'), ton code n'en trouve que 9. Donc il ne prend pas en compte les combinaisons commençant par 'C'.

Ou peut-être est-ce moi qui ne comprend pas tout (c'est fort probable).


EDIT: Toutes mes escuses, cela fonctionne bien après une petite modification du code. J'ai remplacer la condition de sortie par :

Code :

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

1
2
 
$i <= (Nombre de combinaison voulu - 1)

Dans ce cas on trouve bien toutes les combinaisons possibles.

Je te remercie infiniment pour ton aide

Amicalement marsupio,

[etaty]

oui cette condition est fausse :

Code :

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

$TableauValeur[1] != 'c'

sinon tu peut arrêter le script à la plus grand bonne valeur connu :
5C 6B 10A
(donc avec un tableau valeur de fin)

[JeitEmgie]

Ton problème vient de ton algorithme :
tu cherche à trouver toutes les combinaisons possible d'un dé
par à jeter de dé
(code : shuffle($TableauValeur);//mélange aléatoirement les valeurs du tableau)
ce qui n'est pas du tout le meilleur chemin pour y arriver !!!
(qui te dit que tu ne va pas sortir 5000 fois la valeur "5" du dé avant d'avoir enfin ta valeur "6" ?
(d'où le temps de calcul qui varie comme tu l'a expliqué plus haut !)

Maintenant la vrai solution (plus simple et plus rapide) est de passer par un comptage :
A->0
B->1
C->3

tu compte en trinaire

Donc tu compte de 0 à jusqu'à 333 333 333 333 333 333 333 (21 fois la valeur 3)

Puis dans un second temps tu ne sélectionne que les combinaisons qui n'ont que 5 fois le chiffre 3 et ainsi de suite

une solution indépendante de l'alphabet de départ serait en pseudo code :

on définit un alphabet comme la liste des caractères à utiliser (les 10A, 6B, 5C dans ce cas-ci)

fonction calcul_arrangements: IN alphabet de départ

stackAlphabets : un stack d'alphabets
stackClés : un stack de string
(vous aussi pouvez faire un seul stack de d'objets contenant la string et l'alphabet)
solutions : ensemble de string qui contiendra les solutions, initialisé à vide

mettre sur les stacks resp. une chaîne vide et l'alphabet de départ

tant que le stack des alphabets n'est pas vide
alphabetCourant <- pop du stack des alphabets
cléCourante <- pop du stack des clés

caractèresDistincts <- ensemble des caractères distincts de l'alphabet courant (au départ on aura donc {A,B,C})

pour chaque caractère c de caractèresDistincts
nouvelAlphabet <- alphabetCourant \ { c }
nouvelleClé <- concaténation( cléCourante , c)
si (nouvelAlphabet est vide) alors
solutions <- ajouter(solutions , nouvelleClé)
sinon
push(stackAlphabets, nouvelAlphabet)
push(stackClés, nouvelleClé)
fsi
fpour

retourner solutions
ffonction

si vous voulez un fonctionnement de style iterator, il suffit d'implementer l'algorithme dans un objet qui gardera l'état courant… (que les variables locales de la fonction soit des attributs de l'objet…)
et ainsi vous ne devez hardcoder les tests sur les valeurs du vocabulaire dans l'algorithme…
et si vous travaillez en pur OO, l'alphabet peut être constitué de n'importe quel type de données… du moment que l'on puisse les mettre dans un SET (pour l'étape des "caractères" distincts il faut qu'on puisse les tester pour une égalité qui ne soit pas celle de l'adresse mémoire mais bien de leur valeur sémantique…)

FYI, en Java pour le problème en question :

A10 B6 C1 Generation takes: 2.36 secs for 136136
A10 B6 C2 Generation takes: 19.963 secs for 1225224
A10 B6 C3 Generation takes: 123.371 secs for 7759752
A10 B6 C4 Generation takes: 601.71 secs for 38798760
A10 B6 C5 Generation takes: 2497.577 secs for 162954792

(notez les 20 sec pour > 1 million à comparer aux 30 secs pour 80000… et qu'il a fallu quand même allouer 2Gb à la JVM pour la combinaison A10 B6 C5…)

[Montor]

Bonjour
Tu peux nous envoyer les dix premieres combinaisons dans l'ordre ?

[marsupio49]

Là ça devient trop compliqué pour moi lol, j'ai casiment rien compris au post de JeitEmgie
Mais j'ai ben vu que tu ne mettais que 41 minutes pour avoir toutes les combinaisons donc ça m'intéresse lol.

Je me replonge dedans jeudi car là je dois préparer mes oraux de mercredi pour mon BTS informatique.

Merci beaucoup de votre aide,

Amicalement marsupio,

[Montor]

Bonjour

Voici cette fonction qui calcule les combinaison pour "A" et "B ou C" en vba
Voir ici
pour A

Code :

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

1
2
3
 
nb_total_systeme = 21
nb_systeme = 10

pour B ou C

Code :

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

1
2
nb_total_systeme = 11
nb_systeme = 6

le calcule pour "A" donne 352716 combi,pour "B"est 462 combi au total ça fait 352716 *462 donne 162954792
pour le rest tu vas combiner les deux tableaux.

Moi je metrise mal le php mais voici une essai elle fonctionne comme celle de vba
Si tu peux redeclarer le variable $inp
$inp produit une erreur de signe si on change le dernier bit alors il est imposible de sortir de la boucle "while".

Pour A
1023 = 000000000001111111111b; debut
2095104 = 111111111100000000000b; fin
les uns representes le lettre "A" les zeros seront remplacer par le deuxieme tableaux

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
 <?php 
//1023/2095104
$TableauCombinaisonA = array();
$inp=1023;
while($inp<=2095104)    {
$cunt=0;$havef=false;$ww=0;
for ($i = 1; $i <= 21; $i++ ){
if (($inp & 1)&&1){$cunt=$cunt+1;$havef=true;}
elseif($havef){$ww=$i;break;}
$inp>>=1;
    };
	$inp |= 1; $inp<<=$ww-1;
    $inp=(pow(2,$cunt-1)-1)|$inp;	
array_push($TableauCombinaisonA,$inp);//insertion
}
?>

example pour afficher le resultat

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
 <?php 
 
$TableauCombinaisonA = array();
$inp=2098175;
while($inp<=2195104)    {
$cunt=0;$havef=false;$ww=0;
for ($i = 1; $i <= 21; $i++ ){
if (($inp & 1)&&1){$cunt=$cunt+1;$havef=true;}
elseif($havef){$ww=$i;break;}
$inp>>=1;
    };
	$inp |= 1; $inp<<=$ww-1;
    $inp=(pow(2,$cunt-1)-1)|$inp;	
//array_push($TableauCombinaisonA,$inp);//insertion
echo decbin($inp)."<br>";
}
?>

[marsupio49]

Par curiosité, ton programme met combien de temps à trouver 162 954 792 combinaisons?

Je vais essayé de voir l'erreur en PHP et de la corriger pour voir ce que ce programme donne.

Merci,

Amicalement marsupio,

[Montor]

je rectifie pour moi
c'était pas 2095104 combi
mais bien 352716
oublie ça et essaie ce code
$Apage est le nombre de combinaison de A
tu peux le mettre a 352716 pour generer toutes les combinaison
Le code pour 1000*462 combinason

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
53
54
55
56
57
58
 <?php 
//1023/2095104
 
$TableauCombinaisonA = array();
$TableauCombinaisonBC = array();
$Apage=1000;
$inp=63;
$Sys=11;
for ($k = 1; $k <= 462; $k++ )  {
array_push($TableauCombinaisonBC,$inp);
$cunt=0;$havef=false;$ww=0;
for ($i = 1; $i <= $Sys; $i++ ){
if (($inp & 1)&&1){$cunt=$cunt+1;$havef=true;}
elseif($havef){$ww=$i;break;}
$inp>>=1;
    };
	$inp |= 1; $inp<<=$ww-1;
    $inp=(pow(2,$cunt-1)-1)|$inp;	
 
}
 
///
 
$inp=1023;
$Sys=21;
for ($k = 1; $k <= $Apage; $k++ )  {
array_push($TableauCombinaisonA,$inp);
$cunt=0;$havef=false;$ww=0;
for ($i = 1; $i <= $Sys; $i++ ){
if (($inp & 1)&&1){$cunt=$cunt+1;$havef=true;}
elseif($havef){$ww=$i;break;}
$inp>>=1;
    };
	$inp |= 1; $inp<<=$ww-1;
    $inp=(pow(2,$cunt-1)-1)|$inp;	
 
}
//combinaison
for ($ig = 0; $ig <= $Apage-1; $ig++ ){
for ($ik = 0; $ik <= 461; $ik++ ){
$tss=$TableauCombinaisonA[$ig];
$tssf=$TableauCombinaisonBC[$ik];$Str="";
for ($pp = 1; $pp <= 21; $pp++ ){
if (($tss & 1)&&1){$Str.="A" ;}
else
 {
 if (($tssf & 1)&&1){$Str.="B" ;$tssf>>=1;}
else
   { $Str.="C";
     $tssf>>=1;};
   }
 $tss>>=1;
     }
	echo  $Str.'-';
	 } 
}
 
?>

[JeitEmgie]

Bonjour
Tu peux nous envoyer les dix premieres combinaisons dans l'ordre ?

ordre de sortie en partant de l'alphabet A…AB…BC…C en entrée :

BBBBBBCCCCCAAAAAAAAAA
BBBBBBCCCCACAAAAAAAAA
BBBBBBCCCCAACAAAAAAAA
BBBBBBCCCCAAACAAAAAAA
BBBBBBCCCCAAAACAAAAAA
BBBBBBCCCCAAAAACAAAAA
BBBBBBCCCCAAAAAACAAAA
BBBBBBCCCCAAAAAAACAAA
BBBBBBCCCCAAAAAAAACAA
BBBBBBCCCCAAAAAAAAACA
BBBBBBCCCCAAAAAAAAAAC
BBBBBBCCCACCAAAAAAAAA
BBBBBBCCCACACAAAAAAAA
BBBBBBCCCACAACAAAAAAA
BBBBBBCCCACAAACAAAAAA
BBBBBBCCCACAAAACAAAAA
BBBBBBCCCACAAAAACAAAA
BBBBBBCCCACAAAAAACAAA
BBBBBBCCCACAAAAAAACAA
BBBBBBCCCACAAAAAAAACA
BBBBBBCCCACAAAAAAAAAC
BBBBBBCCCAACCAAAAAAAA
BBBBBBCCCAACACAAAAAAA
BBBBBBCCCAACAACAAAAAA
BBBBBBCCCAACAAACAAAAA
BBBBBBCCCAACAAAACAAAA
BBBBBBCCCAACAAAAACAAA
…



le fichier généré fait 3.585.005.424 octets…


PS
si l'ordre peut paraître illogique c'est dû au fait que l'implémentation utilise un Set qui lui se base sur un hashcode pour vérifié l'unicité… l'ordre d'itération sur le Set dépend donc lui aussi indirectement de cet hashcode…

pour avoir le résultat dans l'ordre :
le mieux est d'insérer directement à la bonne place dans une seule liste pour éviter les probs de mémoire… mais cela aura un coût non négligeable sur les perfs…

je doute qu'en PHP vous puissiez garder les résultats en mémoire sauf en version 64 bits… (l'OS ET l'interpréteur PHP…)

[Montor]

je doute qu'en PHP vous puissiez garder les résultats en mémoire sauf en version 64 bits… (l'OS ET l'interpréteur PHP…)

Oui je confirme ce que tu as dis et meme il sera difficile pour les enregistrer dans des fichiers la seul solution pour moi c'est de generer ces combinison par pagination non?
Voici une autre solution sans echo de l'affichge il y a 13860462 combi par minute
ce test donne 1386000 en 50s

[JeitEmgie]

Oui je confirme ce que tu as dis et meme il sera difficile pour les enregistrer dans des fichiers la seul solution pour moi c'est de generer ces combinison par pagination non?

530,3 Mb une fois zippé, mais non encore trié…
pour le trier : split, trier chaque segment et puis un merge…

comme au temps du tri sur bandes magnétiques…


question subsidaire au problème :

faire l' algorithme capable de commencer à la Nème solution sans calculer les N-1 précédentes (en considérant N dans l'ordre lexicographique des tokens de l'alphabet… )

[Montor]

Bonjour
tu peux teste ça JeitEmgie

Le temps d'execution pou ces 162954792 combi mais avec " echo "";" sur mon pc de 2Ghz et 128 MB RAM est de 23 minutes.

pour la conclusion Voici une methode qui vous permettre de selectionner une plage de combinaison pour l'afficher il y a deux page "hash_pages.php et view.php" elles sont liées entre elles

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
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
 hash_pages.php
<?php 
$TableauCombinaisonBC = array();
$inp=63;
$Sys=11;
for ($k = 1; $k <= 462; $k++ )  {
$Str='';$inps=$inp;
for ($i = 0; $i <= $Sys-1; $i++ ){
if (($inps & 1)&&1)
{$tttt[$i]="B";}
else
{$tttt[$i]="C";}
$inps>>=1;
    };	
array_push($TableauCombinaisonBC,$tttt);
$cunt=0;$havef=false;$ww=0;
for ($i = 1; $i <= $Sys; $i++ ){
if (($inp & 1)&&1){$cunt=$cunt+1;$havef=true;}
elseif($havef){$ww=$i;break;}
$inp>>=1;
    };
	$inp |= 1; $inp<<=$ww-1;
    $inp=(pow(2,$cunt-1)-1)|$inp;	
 }
 
/// 
 
 
function setlink($link,$hint){
$hin=implode($hint,'');
$outs='<td title= "de:AAAAAAAAAA'.$hin.chr(13).'  &agrave;:'.$hin.'AAAAAAAAAA" >[<a href="view.php?hash='.implode($hint,'-').'"target="view.php"><span class="Style4">'.$link.'</span></a>]</td>';
return $outs;
}
 
?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>Document sans titre</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css">
<!--
.unn {
	text-align: center;
	}
a:link {
	text-decoration: none;
}
a:visited {
	text-decoration: none;
}
a:hover {
	text-decoration: underline;
	color: #3D78B4;
}
a:active {
	text-decoration: none;
}
body {
	background-color: #FFBFBF;
}
 
.Style4{
color:#3D78B4;
}
 
-->
</style>
</head>
 
<body >
<table width="200" border="0" align="center" cellpadding="0" cellspacing="2" bordercolor="#000000" class="unn">
  <?php $ss=0;
for ($i = 1; $i <=22; $i++ ){ 
  echo '<tr>';
    for ($j = 1; $j <=21; $j++ ){
 
	$mw=$TableauCombinaisonBC[$ss];
	$ss++;
   echo  setlink($ss,$mw);
    }
 echo '</tr>';
 
 }?>
</table>
 
 
 
 
</body>
</html>

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
 view.php
<?php 
if ($_GET['hash']!=""){
Set_Time_Limit(0);
$rempl=explode('-',$_GET['hash'],11);
$AAA=array("A","A","A","A","A","A","A","A","A","A");
$merged=array_merge($AAA,$rempl);
for ($q = 0; $q <= 352715; $q++ )  {
echo implode($merged,'')."-";//Affichage
$cunt=0;$havef=false;$ww=0;
for ($k = 0; $k <= 20; $k++ )  {
if($merged[$k]==='A'){$cunt++;$havef=true;}
elseif($havef){$ww=$k;break;}
            }
$tmps=$ww-$cunt;
$cunt--;
for ($kD = 0; $kD <= $tmps; $kD++ )  {
$merged[$kD+$cunt]=$rempl[$kD];
          }
for ($kD = 0; $kD <= $cunt-1; $kD++ )  {
$merged[$kD]='A';
             }
$merged[$ww]='A';
}
}else{
echo '<style type="text/css">
<!--
.Style1 {
	font-size: 18px;
	font-weight: bold;
}
.Style2 {color: #FF0000}
-->
</style>
<div align="center" class="Style1">
<p>Utiliser la page<a href="hash_pages.php"> <span class="Style2">hash_page</span></a> pour appeler cette page . </p>
</div>';
 
 
;}
?>

[JeitEmgie]

Bonjour
tu peux teste ça JeitEmgie

Le temps d'execution pou ces 162954792 combi mais avec " echo "";" sur mon pc de 2Ghz et 128 MB RAM est de 23 minutes.

c'est normal qu'en optimisant pour le cas particulier de l'énoncé on aille plus vite qu'une solution qui va dans le sens de la généralisation…
dans laquelle les tokens (les A,B,C…) peuvent être n'importe quel type d'objet du moment qu'ils soient ordonnables et que l'on définisse un opérateur de concaténation…

quant au tri, en rajoutant l'opérateur de comparaison comme paramètre, on peut sortir les résultats en ordre croissant ou décroissant et cela quel que soit l'ordre des tokens dans l'alphabet fourni au départ et sans devoir stocker les résultats… et si on ne stocke pas les résultats on n'a évidemment pas de problème de mémoire…

… je préfère donc ma petite solution, pure OO et 100% réutilisable…