Page 1 sur 1
Arbre Lexicographique Generalisé... What is it?
Publié : ven. 21/janv./2005 22:51
par Torp
Salut,
sur cette page
http://lwh.free.fr/pages/algo/minmax/scrabble.htm, il décrit la méthode utilisée, dans des jeux type scrabble, permettant à l'ordinateur de trouver toutes les combinaisons de mots possibles à partir d'un nombre de lettre défini. Cette méthode est appelée ARBRE LEXICOGRAPHIQUE GENERALISE...
Quelqu'un connait il ce truc (la page en question est assez succinte...)? Ceci m'aiderait pour la réalisation de mon prog.
++
Torp
Publié : ven. 21/janv./2005 23:04
par comtois
http://www.chambily.com/recursivite/
Jette un oeil là , au chapitre
Arbres VII-4
Publié : ven. 21/janv./2005 23:20
par Torp
Bon je vais essayer d'éplucher ca. (Le delphi connait pas du tout, mais ca a l'air assez similaire au basic)
Merci Comtois... Décidement... Ca fait deux fois que tu me donnes un sacré coup de pouce... Ton nom secret ce serait pas Zorro...
Merci
++
Torp
Publié : ven. 21/janv./2005 23:28
par Backup
ya quelque temps j'avais posté ça !! (en Mode console mais facilement transposable !)
ps: le miens est mieux puisque le nombre de lettre n'a pas d'importance
Code : Tout sélectionner
;anagrame Realisé par Dobro
Resultat = OpenConsole()
Print("Entrez un mot et appuyez sur 'Return': ")
m$=Input()
n= Len(m$)
Dim mo$(n)
Dim p(n)
mo$(n)=m$
Z=n
rt:
p(Z)=1
dt:
mo$(Z-1)=Right(mo$(Z),Z-1)
Z=Z-1
If Z>1
Goto rt
EndIf
m$=""
For w=1 To n
m$=Left(mo$(w),1)+m$
Next w
Print(m$+" ")
gt:
mo$(Z+1)=mo$(Z)+Left(mo$(Z+1),1)
Z=Z+1
p(Z)=p(Z)+1
If p(Z)<=Z
Goto dt
EndIf
If Z<n
Goto gt
EndIf
Print("FINI !!!!")
k$=Input()
Resultat = CloseConsole()
Publié : ven. 21/janv./2005 23:42
par Torp
Oui mais d'apres ce que j'ai compris, avec la méthode de l'ALG, ca permet de trouver tout les mots VALIDES, basés sur un DICO.
Par exemple avec 6 Lettres au hasard, trouver tous les mots éxistant (dans le dico) de 2,3,4,5 et 6 lettres.
Publié : sam. 22/janv./2005 0:21
par Backup
ben la t'a plus qu'a comparer chaque resultat avec une liste de mots d'un dictionnaire c'est facile !
avec mon prg tu tappe "dobro"
il te sort comme resultat :
"Dobro" << tu compare ce resultat avec une liste de mots du dico
c'est simple tu parcour toute la liste du dico pour voir si ce mot s'y trouve !
puis "dobor" << pareil avec celui la
puis "dorob" << pareil avec celui la
ect ...
jusqu'a la fin des possibilité sorti par mon prg !
la seul chose c'est qu'a chaque resultat donné par mon prg
il te faudra rajouter la possibilité de comparer ce resultat au dico
mais aussi ce resultat moins 1 lettres , moins 2 lettres ,ect jusqu'a 2 lettres
c'est franchement pas tres dur ! grace a " FindString(Chaine$, ChaineCherchee$, PositionDepart)
" commande toute faite du purebasic !
Publié : sam. 22/janv./2005 0:41
par Torp
Suis d'accord avec toi, mais disons qu'avec 6 lettres tu peux faire 720 anagrammes de 6 lettres à comparer aux quelques 110000 mots de mon dico... et je te parle pas de tous les anagrammes possibles de 2,3,4,et 5 lettres parmi ces 6 lettres
Je cherchais un manière plus ... académique...
Publié : sam. 22/janv./2005 0:46
par Backup
je comprend
mais tu sais la fonction " FindString(Chaine$, ChaineCherchee$, PositionDepart) " du pure est incroyablement rapide !!
je m'en sert dans mon synthetiseur vocale , et il s'agis d'avoir la reponse quasi instentanée pour que la syllabe trouvé puisse etre parlé par mon synthe vocale !
et ça marche tres bien c'est tres fluide , a vrai dire je suis obliger de ralentir
l'analyse des mots des phrase, car c'est trop rapide, par rapport au temps de diffusion de la sonorité de la syllabe !
pour un mot de 10 lettres toute les occurence de ce mot sont analysé en 14 secondes environ sur mon pc (2.8 go)!!!
ça va pas chercher loin !!
si tu rajoute l'analyse des resultats en decroissant la longueur du mot
on doit perdre 4 ou 5 secondes suplementaire !
bref dans le pire des cas (mot de 11 lettres) ça mettrai au bas mot 25 ou 30 secondes pour mon algo , et peut etre autant pour trouver le mot dans le dico ! , faudrai essayer pour voir !
;D
Publié : sam. 22/janv./2005 0:55
par Torp
De toute façcon comme je suis un quiche en math... il est très possible que je me rabatte sur la mèthode plus ... "force brute"
. Euh Pardon .... "Force PURE" !
Publié : sam. 22/janv./2005 1:04
par Backup
en fait ce serai plus simple d'avoir a analyser que les mots de la longueur entré
genre "Dobro" = 5 Lettres , et comparer avec le dico ces 5 lettres la
bien sur on pert du temps s'il faut comparer avec le dico
"dobro"
"dobr"
"dob"
"do"
et ce pour chaque resultat !
en fait c'est pas utile dans le cadre du scrable !
on pourrai gagner dela vitesse en ne comparant qu'avec les mots du dico de la mem longueur , ce qui force a trier le dico par longueur de mots !
mais apres la recherche serai tres simplifié , donc rapide !
ps : mon prg etait prevu pour ça a l'origine ( bruteforce dans un but pedagogique bien sur ! )
Publié : sam. 22/janv./2005 9:57
par comtois
Torp a écrit :De toute façcon comme je suis un quiche en math... il est très possible que je me rabatte sur la mèthode plus ... "force brute"
. Euh Pardon .... "Force PURE" !
Si tu as besoin d'un exemple pour construire le dictionnaire et l'afficher , n'hésite pas à demander .
Publié : sam. 22/janv./2005 10:33
par comtois
Comme le sujet m'intéressait , je viens de faire un petit essai
http://purebasic.hmt-forum.com/viewtopic.php?p=21262
Publié : dim. 23/janv./2005 0:37
par Torp
Vais aller voir ça. Encore Merci.