Scrabble (toutes les possibilités) [Résolu]

Messages postés
180
Date d'inscription
samedi 22 novembre 2003
Dernière intervention
25 juin 2017
- - Dernière réponse : moi411
Messages postés
180
Date d'inscription
samedi 22 novembre 2003
Dernière intervention
25 juin 2017
- 24 oct. 2010 à 19:50
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
Afficher la suite 

Votre réponse

8 réponses

Meilleure réponse
Messages postés
835
Date d'inscription
samedi 15 novembre 2008
Dernière intervention
14 janvier 2017
3
Merci
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

/// <summary>
/// retourne une liste d'arrangements
/// </summary>
/// contient l'historique des lettres prélevées à chaque niveau


/// le lettres à permuter


/// <returns></returns>
private static  List<string> Combinaison( string prefix, string toArrange)
{
//une lettre ? facile on la retourne en concatenant le prefix
if (toArrange.Length == 1)
return new List<string>(new string[] { prefix+toArrange});
else // on permute
{
List<string> ret = new List<string>();
// 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<string> Combinaisons=Combinaison( "", "ABCDE");
bon ça à l'air de le faire....

Bob
C# is amazing, enjoy it!

Merci cs_Robert33 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources a aidé 100 internautes ce mois-ci

Commenter la réponse de cs_Robert33
Messages postés
835
Date d'inscription
samedi 15 novembre 2008
Dernière intervention
14 janvier 2017
3
Merci
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!

Merci cs_Robert33 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources a aidé 100 internautes ce mois-ci

Commenter la réponse de cs_Robert33
Messages postés
24
Date d'inscription
mercredi 4 juin 2008
Dernière intervention
19 avril 2011
0
Merci
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
Commenter la réponse de cs_vikking
Messages postés
180
Date d'inscription
samedi 22 novembre 2003
Dernière intervention
25 juin 2017
0
Merci
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
Commenter la réponse de moi411
Messages postés
835
Date d'inscription
samedi 15 novembre 2008
Dernière intervention
14 janvier 2017
0
Merci
Humm petit bug, si on a 2fois la même lettre.
mais je vous laisse chercher la solution

Bob
C# is amazing, enjoy it!
Commenter la réponse de cs_Robert33
Messages postés
180
Date d'inscription
samedi 22 novembre 2003
Dernière intervention
25 juin 2017
0
Merci
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
Commenter la réponse de moi411
Messages postés
180
Date d'inscription
samedi 22 novembre 2003
Dernière intervention
25 juin 2017
0
Merci
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
Commenter la réponse de moi411
Messages postés
180
Date d'inscription
samedi 22 novembre 2003
Dernière intervention
25 juin 2017
0
Merci
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
Commenter la réponse de moi411

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.