### 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