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

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