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
lander –> a1
Earth –> a1
antsier –> a1
Heart –> a1
asterin –> a1
randel –> a1
sort and put in a2
Now sort a2 accordin to the str in it simlilary change a1
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