TROUVER TOUS LES ANAGRAMMES D'UN MOT (AVEC DICO)
Debiars
Messages postés
285
Date d'inscription
lundi 16 juin 2003
Statut
Membre
Dernière intervention
11 février 2018
-
30 août 2005 à 16:59
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 9 janv. 2010 à 23:05
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 9 janv. 2010 à 23:05
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/33526-trouver-tous-les-anagrammes-d-un-mot-avec-dico
https://codes-sources.commentcamarche.net/source/33526-trouver-tous-les-anagrammes-d-un-mot-avec-dico
9 janv. 2010 à 23:05
Grande plaisanterie que tout cela.
9 janv. 2010 à 22:27
Il suffit de trier les lettres d'un mot dans l'ordre lexicographique.
Exemple :
amer -> aemr
rame -> aemr
mare -> aemr
maree -> aeemr
Les anagrammes auront donc la même empreinte (le même hash).
On range çà dans une table de hachage (une std::map par exemple)
On a accès en temps constant à la liste des anagrammes d'un mot en calculant son hash
C'est ultra compacte. Le programme tient en une dizaine de ligne.
LireDico(const File *iDico,std::map<string,string>& oTable )
string hash,mot;
while(!NotEnded(iDico) )
LectureLigne(iDico,mot)
CalculerEmpreinte(mot,hash)
oTable.insert(hash,mot);
CalculerEmpeinte(const string& iMot, string& oHash)-> string
...
RetrouverAnagrammes(const string& iMot,
const std::map<...>& iTable,
std::list<string>& oAnagrammes)
string hash;
CalculerEmpreinte(iMot,hash);
std::map<...>::iterator it=iTable.find(hash);
while ( it!= iTable.end() )
oAnagrammes.push_back(it->second);
Voilà franchement 5 minutes à coder et beaucoup plus rapide (a optimiser si on veut en compressant les mots)
6 août 2008 à 09:33
2 déc. 2005 à 04:08
8 sept. 2005 à 08:31
Ce n'est pas le langage mais du format de fichier dont je te parlais, 1 mot par ligne oblige à une recherche de fin de ligne pour extraire le mot suivant. Essaie avec une table en début de fichier indiquant combien de chaque longueur et ainsi tu peux coller tous les mots et les extraire juste au moment de la recherche, plus besoin de tout mettre en mémoire et c'est hyper rapide.
8 sept. 2005 à 00:51
c'est juste malheureux que ce soit pas en delphi BruNews moi et le vb ...pas sûr ...comment comparer des pommes avec des oranges ? question temps ça m'a l'air bien aussi quoique c'est pas pareil du tout ...
7 sept. 2005 à 23:52
http://www.cppfrance.com/code.aspx?ID=31892
ça fait aussi les anagrammes entre autre.
Pourquoi ton dico est au format 1 mot par ligne ? c'est très lent d'accès en lecture et ça grossit la taille du dico inutilement.
7 sept. 2005 à 23:19
j'ai bidouillé encore car ce truc m'intéresse énormément et à force de tourner en rond avec ces possibilités ,j'ai creer un autre arbre en limitant les nodes à celles de l'anagramme puis j'ai cliqué ...Je parcours maintenant le dico qu'une seule fois node par node ,si c'est impossible je saute à la branche suivante ,et en prime j'obtiens classer en ordre alphabétique une liste sans doublons ...
Le temps de recherche pour "anticonstitutionnellements" n.est pas plus long que la création du dico !!!
1er filtre en parcourant le dico:
var
MySet: set of 'A'..'Z';
MySet :=[];
for x:=0 to length(ANAGRAMME)do
begin
if not (ANAGRAMME[x+1] in MySet)then
MySet :=MySet + [ANAGRAMME[x+1]];
end;
et en parcourant le dico je teste :
if not(T^.Lettre in MySet )then break;
se qui conduit à la branche suivante...
le deuxiemme filtre, là, j'ai pas trouvé mieux :
je compare les lettres de l'anagramme avec les lettres
du mot en mémoire...
Function Compare(Mot:String;ANA:String):Boolean;
var
a,b:Integer;
begin
result:=false;
for b:=length(Mot) downto 1 do
begin
for a:=1 to length(ANA)do
begin
if (mot[b]=ANA[a])then
begin
setlength(mot,length(Mot)-1);
//pour une fois que le downto est utile
ANA[a]:='?';
//pour dire qu'utiliser
break;
end;
end;
if(mot='')then
begin
result:=true;
exit;
end;
end;
end;
ps:vérifie ton dico certains mots ont plus de 27 lettres
et sont en doubles...
Pour le code au complet comme le mérite te reviens je te l'envoi quand tu voudras ...
pour les autres on verra , lol ...
Yve
3 sept. 2005 à 18:41
Creer_Poss(UpperCase(edText.Text),1,length(edText.Text),'');
renvoi dans une TStringList toutes les possibilités...
procedure Creer_Poss(Mot:String;n:Integer;lg:Integer;nouveauMot:String);
var
temp:String;
i,j,k,m:Integer;
begin
if(lg<>0)then
begin
for i:=1 to lg do
begin
setlength(nouveauMot,n);
nouveauMot[n]:=Mot[i];
temp:='';
for m:=1 to n do temp:=temp+nouveauMot[m];
//if(Dico(temp)=true)then
strList.Add(temp);
k:=1;
for j:=1 to lg do
begin
if(j<>i)then
begin
setlength(temp,k);
temp[k] := Mot[j];
inc(k);
end;
end;
Creer_Poss(temp, n+1, lg-1, nouveauMot);
end;
end;
end;
30 août 2005 à 20:27
Merci du commentaire :) Abened
30 août 2005 à 16:59
Pour éviter d'afficher les doublons, une petite procédure toute simple pour vérifier s'il ne figure pas déjà dans la liste :
procedure AfficheMot(str : string);
var i : integer;
begin
for i := 0 to form1.lbResult.Items.Count-1 do
if str = form1.lbResult.Items[i] then Exit;
form1.lbResult.Items.Add(str);
end;
procedure RecurMot(Node : TAnaNode; str : string);
var i : integer;
begin
if Node.Level>0 then str:=str+Node.Letter;
if Node.Style=nsLeaf then AfficheMot(str) // ligne modifiée
bye :-D