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

Messages postés
3238
Date d'inscription
jeudi 26 novembre 2009
Dernière intervention
14 mars 2018
- 20 févr. 2014 à 14:54 - Dernière réponse :
Messages postés
3238
Date d'inscription
jeudi 26 novembre 2009
Dernière intervention
14 mars 2018
- 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 

Votre réponse

7 réponses

Messages postés
3238
Date d'inscription
jeudi 26 novembre 2009
Dernière intervention
14 mars 2018
- Modifié par cs_ShayW le 20/02/2014 à 15:32
0
Merci
peut etre
il faut verifier plutot si chaque mot du dico contient les lettres
distribuées
Messages postés
12247
Date d'inscription
jeudi 15 mai 2008
Statut
Modérateur
Dernière intervention
2 novembre 2018
- 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.
Messages postés
12247
Date d'inscription
jeudi 15 mai 2008
Statut
Modérateur
Dernière intervention
2 novembre 2018
- 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...
Messages postés
23256
Date d'inscription
mercredi 22 octobre 2003
Statut
Modérateur
Dernière intervention
17 novembre 2018
- 20 févr. 2014 à 16:13
Messages postés
12258
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
17 novembre 2018
- 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
Messages postés
199
Date d'inscription
mercredi 23 avril 2003
Statut
Contributeur
Dernière intervention
25 mai 2017
- 23 févr. 2014 à 10:51
0
Merci
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
Messages postés
3238
Date d'inscription
jeudi 26 novembre 2009
Dernière intervention
14 mars 2018
- 23 févr. 2014 à 15:37
0
Merci
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.