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:

Ca peut servir mot le plus long
Ca peut servir le mot le plus long - Meilleures réponses
Mot le plus long ca peut servir - Meilleures réponses
Ça peut servir mot le plus long - Forum C++ & C++ .NET
Ca peut servir mots le plus long - Forum Delphi / Pascal
Anagrammes - Forum PHP
Comment reconnaitre un mot dans une chaine - Forum Visual Basic
Long et timestamp - Forum Java

3 réponses

Réponse 1 / 3

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

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.

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...

jordane45 Messages postés 38145 Date d'inscription mercredi 22 octobre 2003 Statut Modérateur Dernière intervention 25 avril 2024 344
20 févr. 2014 à 16:13

Niveau requête ça rejoint aussi une question que j'ai posé récement :
http://codes-sources.commentcamarche.net/forum/affich-10020130-mysql-recuperer-les-enregistrement-repondant-a-un-array#p10020571

Ou une autre discussion encore plus "proche" de ce que tu cherches :
http://www.developpez.net/forums/d1210838/bases-donnees/langage-sql/mots-contenant-certaines-lettres/

Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 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.

Réponse 2 / 3

carlvb Messages postés 199 Date d'inscription mercredi 23 avril 2003 Statut Contributeur Dernière intervention 25 mai 2017 11
23 févr. 2014 à 10:51

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

Discussions similaires

traitement de mot

parcourir une chaîne de caractère lettre par lettre

Lire un fichier mot par mot

générer une grille de mots mêlés

Requete SQL pour recherce une chaine avec caractères spéciaux

Cherche mélangeur de mots à partir d'un texte existant ou un reformulateur de te

Votre réponse

Discussions similaires