Algo pour trouver les mots le plus long [Résolu]

cs_ShayW 3238 Messages postés jeudi 26 novembre 2009Date d'inscription 14 mars 2018 Dernière intervention - 20 févr. 2014 à 14:54 - Dernière réponse : cs_ShayW 3238 Messages postés jeudi 26 novembre 2009Date d'inscription 14 mars 2018 Dernière intervention
- 23 févr. 2014 à 15:37
Bonjour,

Dans le cadre d'une amélioration du jeu des chiffres et des lettres que j'avais
déposé je cherche un algo rapide pour trouver les mots le plus long.
Jusqu'à présent je procède ainsi
J'ai 10 lettres et 8 dico ( une liste de string)
je trouve les combinations de 2,3,4,5,6,7,8,9,10 lettres
dans une boucle
pour chaque combination je calcule les permutations
dans une boucle
pour chaque element de la permutation je verifie si
si l'element existe dans un dico

le temps execution est un peu long
ex : si j'ai 10 lettres différente j'ai 10! arrangements possible
et qu'il y a seulement des mots de 6 lettres
le temps est de 37 secondes un peu long

Si quelqu'un a une auttre approche

Merci
Afficher la suite 

7 réponses

Répondre au sujet
cs_ShayW 3238 Messages postés jeudi 26 novembre 2009Date d'inscription 14 mars 2018 Dernière intervention - Modifié par cs_ShayW le 20/02/2014 à 15:32
0
Utile
4
peut etre
il faut verifier plutot si chaque mot du dico contient les lettres
distribuées
pijaku 12205 Messages postés jeudi 15 mai 2008Date d'inscriptionModérateurStatut 13 septembre 2017 Dernière intervention - 20 févr. 2014 à 16:04
Bonjour,

Réduire le dico initial semble être une bonne idée.
Tu peux peut être lire ce sujet qui est un peu similaire au tien, particulièrement cette réponse qui explique comment, en VBA, importer des mots, d'un fichier txt, grâce à une requête...
C'est du VBA, mais tu peux très largement t'en inspirer... Ou pas.
pijaku 12205 Messages postés jeudi 15 mai 2008Date d'inscriptionModérateurStatut 13 septembre 2017 Dernière intervention - 20 févr. 2014 à 16:08
à lire également, une requête qui permet le tri par longueur de mots...
Très utile si tu souhaites trouver le mot le plus long, il suffit de commencer ta boucle par la fin...
jordane45 20570 Messages postés mercredi 22 octobre 2003Date d'inscriptionModérateurStatut 21 avril 2018 Dernière intervention - 20 févr. 2014 à 16:13
Whismeril 11411 Messages postés mardi 11 mars 2003Date d'inscriptionContributeurStatut 22 avril 2018 Dernière intervention - 23 févr. 2014 à 11:22
Bonjour, en complément de Pijaku, j'ai posté hier, ma version en C#, qui est proche du VB.net.
Dans la classe tirage, la première réduction du dictionnaire est comme tu l'a envisagé de ne garder que les mots ne contenant que des lettres tirées, (requête Linq + Regex).
A ce moment il te suffit de faire une requête supplémentaire qui retourne le(s) mot(s) le(s) plus long(s).

En c#
            //première réduction du dico avec seulement les lettres tirées sur suggetion de Ucfoutu, utilisation de regex
            string[] alphabet = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };
            var lettres = alphabet.Except(tires.Select(c => c.FaceVisible).Distinct());//liste des lettres non tirées
            Regex maRegex = new Regex(string.Format("^[^{0}]+$",string.Join("",lettres)));
            List<string> dicoExclu = MonDico.Liste.FindAll(c => maRegex.IsMatch(c));

            //recherche des mots les plus longs pour ShayW
            int longeurMax = dicoExclu.Select(c=> c.Length).Max();
            List<string> motsLesPlusLongs = dicoExclu.FindAll(c => c.Length == longeurMax);


En VB via un traducteur:
'première réduction du dico avec seulement les lettres tirées sur suggetion de Ucfoutu, utilisation de regex
Dim alphabet As String() = {"A", "B", "C", "D", "E", "F", _
	"G", "H", "I", "J", "K", "L", _
	"M", "N", "O", "P", "Q", "R", _
	"S", "T", "U", "V", "W", "X", _
	"Y", "Z"}
Dim lettres = alphabet.Except(tires.[Select](Function(c) c.FaceVisible).Distinct())
'liste des lettres non tirées
Dim maRegex As New Regex(String.Format("^[^{0}]+$", String.Join("", lettres)))
Dim dicoExclu As List(Of String) = MonDico.Liste.FindAll(Function(c) maRegex.IsMatch(c))

'recherche des mots les plus longs pour ShayW
Dim longeurMax As Integer = dicoExclu.[Select](Function(c) c.Length).Max()
Dim motsLesPlusLongs As List(Of String) = dicoExclu.FindA


Il y a 323781 mots dans le dictionnaire de Pijaku et la recherche se fait en 100ms environ.
Commenter la réponse de cs_ShayW
carlvb 199 Messages postés mercredi 23 avril 2003Date d'inscriptionContributeurStatut 25 mai 2017 Dernière intervention - 23 févr. 2014 à 10:51
0
Utile
Bonjour,

Voici une méthode qu'on peut utiliser pour trouver tous les mots possibles à partir d'un tirage de n lettres :

- Valoriser les lettres de A à Z à l'aide des nombres premiers successifs (A=2, B=3, C=5,... K=31, L=37... , Y=97 et Z=101.

- Calculer le "poids" de chaque mot dans le dictionnaire en multipliant la valeur des mots qui la composent et les stocker pour ne pas avoir à les recalculer à chaque fois (d'autant plus que ce poids est invariable) :
ex : CA = 2 (C) * 5 (A) = 10
REINDEXEZ = 61 (R) * 11 (E) * 23 (I) * 43 (N) * 7 (D) * 11 (E) * 89 (X) *11 (E) * 101 (Z) = 5052584698777

- Sur le même principe, calculer le poids d'un tirage donné
ex : AZERTYUIO = 73663530001402

- Identifier dans le dictionnaire les mots dont le poids est un diviseur de celui de tirage.
ex : TROUE (163456271), ROYAUTE (31710516574) ou AZOTURIE (759417835066) sont des diviseurs de AZERTYUIO (73663530001402).

La méthode est très rapide, sur Excel il faut moins d'une seconde pour avoir la liste de tous les mots possibles.

Mon explication est certainement flou mais avec un exemple vous devriez comprendre assez facilement (http://cjoint.com/14fe/DBxkqSaGYHb_tirage_9_lettres.xlsx).

Merci
Commenter la réponse de carlvb
cs_ShayW 3238 Messages postés jeudi 26 novembre 2009Date d'inscription 14 mars 2018 Dernière intervention - 23 févr. 2014 à 15:37
0
Utile
Merci à tous

Il me reste plus qu'à décortiquer
Au boulot donc
Commenter la réponse de cs_ShayW

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.