Algo pour trouver les mots le plus long

Résolu
cs_ShayW Messages postés 3253 Date d'inscription jeudi 26 novembre 2009 Statut Membre Dernière intervention 3 décembre 2019 - 20 févr. 2014 à 14:54
cs_ShayW Messages postés 3253 Date d'inscription jeudi 26 novembre 2009 Statut Membre Dernière intervention 3 décembre 2019 - 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
A voir également:

3 réponses

cs_ShayW Messages postés 3253 Date d'inscription jeudi 26 novembre 2009 Statut Membre Dernière intervention 3 décembre 2019 57
Modifié par cs_ShayW le 20/02/2014 à 15:32
peut etre
il faut verifier plutot si chaque mot du dico contient les lettres
distribuées
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
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.
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
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...
0
jordane45 Messages postés 38197 Date d'inscription mercredi 22 octobre 2003 Statut Modérateur Dernière intervention 30 mai 2024 344
20 févr. 2014 à 16:13
0
Whismeril Messages postés 19048 Date d'inscription mardi 11 mars 2003 Statut Contributeur Dernière intervention 30 mai 2024 656
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.
0
Rejoignez-nous