Wednesday, September 13, 2006

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 :D
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 :D 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 :D

0 Comments:

Post a Comment

<< Home