Monthly Archives: July 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

Some Tips for programming

I was doing some programin durin holidays … i have found the following tips on programming maybe it be helpful for you ..

This is my first post in Programming section so i will be adding more tips later in this psot only ..

for this time i am posting two hints .. will post other later

1.Suppose you are in a size contest and you want to take a double array as input ..this one of the minimum wayz you can write the program :-

for ( int i=0 ; i < n*n ; i++) cin>>a[i/n][i%n];

2.Suppose you are given a problem in which you are taking hexa-decimal numbers as input ..and then you need to convert it into decimal number … this is one of the way you can do it :-

scanf(“%X”,&num);

the complier will covert the Hexa number to decimal for you … :D

Sorry ….

I am extremly sorry for not Bloggin for these many dayz¬† … I am lil lazy and i am bit buzy too .. But i promise i will be back soon .. with all the latest news and some hacks .