scrabble (toutes les possibilités)Résolu

Question

Bonsoir,
Je suis en train de faire un programme de scrabble.
Principe, on tire 7 lettres aléatoirement et on cherche toutes les combinaisons possibles.
Mais voilà, jusqu'à maintenant, quand j'ai mes 7 lettres je tire aléatoirement chaque lettre pour les ordonner.

Aléatoirement veut dire qu'on peut tirer plusieurs fois la même lettre; En plus quand j'ai une chaine de 7 lettres je dois la comparer à toutes celles que j'ai déjà trouvées (ce qui peut-être long) pour éviter les doublons! 

D'ou question, existe-il un autre moyen que l'aléatoire? Par exemple un algorythme logique, que je n'ai pas trouvé!

moi

cs_Robert33 · Accepted Answer

Bonjour trouver les combinaisons (ou arrangement en math) c'est s'ammuser a faire les permutations. supposons les cas A => A ok, facile AB => AB; BA; ; bon d'accord ABC => ABC; ACB; BAC; BCA; CAB; CBA humm on remarque que l'algorithme serait de prendre chaque lettre et de les associer avec les permutations des 2 restantes. plus difficile ABCD => ABCD; ABDC; ACBD; ACDB; ADBC; ADCB; BACD; BADC ... la encore, on prend chaque lettre et on associe avec les permutations des 3 restantes Essayons de coder tout ça on va faire un recurcif, à chaque niveau on prend la premiere lettre qu'on va concatener aux arrangements des autres au dernier niveau on doit un avoir plus qu'une... Et a chaque tour on passe les lettres prélevées et celles à permuter ///

/// retourne une liste d'arrangements ///

/// contient l'historique des lettres prélevées à chaque niveau /// le lettres à permuter /// private static List Combinaison( string prefix, string toArrange) { //une lettre ? facile on la retourne en concatenant le prefix if (toArrange.Length == 1) return new List(new string[] { prefix+toArrange}); else // on permute { List ret = new List(); // on prend chaque lettre et on appelle l'arrangement pour les lettres restantes foreach (char c in toArrange) { // la liste de permutations retournées est ajoutée à celles qu'on a déjà. ret.AddRange(Combinaison( prefix + c, toArrange.Replace(c.ToString(),""))); } // on retourne les permutations calculées, elles seront concaténées au niveau au dessus à la lettre prélevée etc... return ret; } } reste à l'appeler List Combinaisons=Combinaison( "", "ABCDE");bon ça à l'air de le faire.... Bob C# is amazing, enjoy it!

cs_vikking · Answer

Bonjour,

Je voudrais savoir si tu as trouvé une solution car de mon cas, j'ai une liste de N entiers , et comme toi je voudrait pouvoir lister toutes possibilités.

Merci à ceux qui pourront m'aider

moi411 · Answer

Et bien non, je n'ai pas trouvé mieux... 

J'ai trouvé quand-même un fichier avec 60000 mots et à chaque fois que la combinaison existe (donc que cette dernière est dans le fichier), je garde en mémoire.

Ensuite je compare avec ce que j'ai déjà concervé pour éviter les doublons... 
C'est toujours aussi long mais je suis sûre de ne pas tomber sur des mots qui n'existent pas...

Le fichier en question, je l'ai trouvé en tapant sur google: "fichier texte scrabble", ou un truc approchant!

Voilà!!! Je suis maintenant bloqué là!
Salut.

moi

cs_Robert33 · Answer

Humm petit bug, si on a 2fois la même lettre.
mais je vous laisse chercher la solution 

Bob
C# is amazing, enjoy it!

moi411 · Answer

Salut,
Et bien je vais essayer ça cette après-midi et on verra si ça me prend moins de qques heures pour pour une dizaine de lettre!!!

Mais merci pour cette nouvelle piste!
A bientôt.

moi

moi411 · Answer

Re,
Effectivement ça marche malgré le petit bug, mais en fait je ne comprends pas la récursivité... Je comprends le principe mais pas dans ce cas, je n'arrive pas à voir comment ça fonctionne!!! 

En attendant la solution au bug en question se trouve dans la fonction "replace" qui remplace tous les caractères passés en paramètre au lieu d'un seul comme on le veut ici... 
Je préconise le remplacement de "replace" par "remove", un compteur déclaré avant le foreach et initialisé à 0 (par exemple i).
Il est incrémenté dans la fonction remove; comme suit: remove(i++, 1); 

Voilà, si tu pouvais me donner de plus amples information sur cette récursivité, parce que là je sèche!!!

Sinon merci encore et à bientôt.
moi

cs_Robert33 · Answer

Bonjour

Effectivement le bug venait de replace, bien vu pour la correction

j'utilise la recursivité car comme expliqué plus haut on doit faire la même chose indépendament du nombre de lettre (sauf si 1)
dans notre cas,

CAS 1 lettre, soit A on la retourne.

CAS 2 lettres, soit AB, on prend chaque lettre et on appelle pour ce qui reste et on concatene la lettre prélevé. Entre parentheze la partie prelevée
_   on preleve A et on appelle pour B => CAS 1 retourne (A)B
_ on preleve B et on appelle pour A => CAS 1 retourne (B)A

CAS 3 lettres, soit ABC
. on preleve A et on appelle pour BC => CAS 2 
.   on preleve B et on appelle pour C => CAS 1 retourne (AB)C
.   on preleve C et on appelle pour B => CAS 1 retourne (AC)B
. on preleve B et on appelle pour AC => CAS 2
.   on preleve A et on appelle pour C => CAS 1 retourne (BA)C
.   on preleve C et on appelle pour A => CAS 1 retourne (BC)A
. on preleve C et on appelle pour AB => CAS 2 
.   on preleve A et on appelle pour B => CAS 1 retourne (CB)C
.   on preleve B et on appelle pour A => CAS 1 retourne (CA)B

CAS 4 lettres, soit ABCD
. on preleve A et on appelle pour BCD => CAS 3
.   on preleve B et on appelle pour CD => CAS 2
.     on preleve C et on appelle pour D => CAS 1 retourne (ABC)D
.     on preleve D et on appelle pour C => CAS 1 retourne (ABD)C
.   on preleve C et on appelle pour BD => CAS 2
.     on preleve B et on appelle pour D => CAS 1 retourne (ACB)D
.     on preleve D et on appelle pour B => CAS 1 retourne (ACD)B
.   on preleve D et on appelle pour BC => CAS 2
.     on preleve B et on appelle pour C => CAS 1 retourne (ADB)C
.     on preleve C et on appelle pour B => CAS 1 retourne (ADC)B

C# is amazing, enjoy it!

moi411 · Answer

Re,
Ah ok, je crois que j'ai compris. 
Je vais quand-même refaire cette fonction (sans regarder évidemment) pour être sûre d'avoir bien compris!

En attendant merci, là c'est devenu efficace!!!
A la prochaine.
moi

Scrabble (toutes les possibilités)

8 réponses

Votre réponse

Discussions similaires