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

Signaler
Messages postés
3258
Date d'inscription
jeudi 26 novembre 2009
Statut
Membre
Dernière intervention
3 décembre 2019
-
Messages postés
3258
Date d'inscription
jeudi 26 novembre 2009
Statut
Membre
Dernière intervention
3 décembre 2019
-
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

3 réponses

Messages postés
3258
Date d'inscription
jeudi 26 novembre 2009
Statut
Membre
Dernière intervention
3 décembre 2019
48
peut etre
il faut verifier plutot si chaque mot du dico contient les lettres
distribuées
Messages postés
12263
Date d'inscription
jeudi 15 mai 2008
Statut
Modérateur
Dernière intervention
14 mai 2020
11
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.
Messages postés
12263
Date d'inscription
jeudi 15 mai 2008
Statut
Modérateur
Dernière intervention
14 mai 2020
11
à 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...
Messages postés
28802
Date d'inscription
mercredi 22 octobre 2003
Statut
Modérateur
Dernière intervention
18 mai 2020
328
Messages postés
14804
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
19 mai 2020
400
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.
Messages postés
199
Date d'inscription
mercredi 23 avril 2003
Statut
Contributeur
Dernière intervention
25 mai 2017
6
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
Messages postés
3258
Date d'inscription
jeudi 26 novembre 2009
Statut
Membre
Dernière intervention
3 décembre 2019
48
Merci à tous

Il me reste plus qu'à décortiquer
Au boulot donc