Knuth’s Algorithm for Anagrams
When i was solving some ACM; problems . I found many angrams problems and some having application of anagrams; .During Holidays i was reading Knuths guide to programming ..and i have found this cool algo.
Suppose a problem is given :-
Given a List of dictionary words ( >1,00,000 words )in a file dict.txt ( say ) . and you have to find out all the anagrams in it .
So here is the Knuths algorithm :-
Store the words in an array a1 (say) sort each and every word and store it in a2. [ I mean to say suppose a1[i]=”dog” sort “dog” and then put a2[i]=”dgo” ]
Now sort array a2 according to the string in it & keep swaping the respective indexes in a1 .
Now compare values in a2 and find whether they are anagram or not that’s it
Example :-
—————————————————————————————
dict.txt :-
lander –> a1[0]
Earth –> a1[1]
antsier –> a1[2]
Heart –> a1[3]
asterin –> a1[4]
randel –> a1[5]
sort and put in a2
a2[0]=adelnr
a2[1]=aehrth
a2[2]=aeinrst
a2[3]=aehrth
a2[4]=aeinrst
a2[5]=adelnr
Now sort a2 accordin to the str in it simlilary change a1
a2[0]=adelnr a1[0]=lander
a2[1]=adelnr a1[1]=randel
a2[2]=aehrth a1[2]=Earth
a2[3]=aehrth a1[3]=Heart
a2[4]=aeinrst a1[4]=antsier
a2[5]=aeinrst a1[5]=asterin
Now compare values of a2 to find the grp of anagrams
according to the example
Grp of anagrams are :-
1 lander and randel
2 Earth and Heart
3 antsier and asterin
If some body has a better algorithm or a better way to improve this code plz write a comment
0 Comments:
Post a Comment
<< Home