Arbre Lexicographique Generalisé... What is it?

[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

[comtois]

http://www.chambily.com/recursivite/

Jette un oeil là , au chapitre Arbres VII-4

[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

[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() 

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

[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 !

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

[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

[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" !

[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 ! )

[comtois]

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 .

[comtois]

Comme le sujet m'intéressait , je viens de faire un petit essai

http://purebasic.hmt-forum.com/viewtopic.php?p=21262

[Torp]

Vais aller voir ça. Encore Merci.