Given an English text print out the list of words and their anagrams in their order of occurrence. Word A is an anagram of word B if it can be derived from word B by merely shuffling the letters in word B?

This can almost be done with some shell stuff : for i in $(cat test.txt) ; do echo $i | tr -cd "[:alnum:]" | tr '[:upper:]' '[:lower:]' |grep -o . | sort |tr -d "\n" ; echo " " $i ; done | sort | uniq | awk 'BEGIN {c=0;prev="";o=""} {if($1==prev) {c++; o=o" "$2} else { if(c>=1) print o; c=0;o=$2} prev=$1;}' | tr '[:upper:]' '[:lower:]' This produces : 24 42deal leadand danparts strap traps The error is that the words aren't printed in order of their real occurrence. The correct solution using proper UNIXese is left as an exercise to the astute reader ;)

Spaces and punctuation marks don't need to be processed. So, first count the actual number of words. Let there be N words. Construct a table of size N x 26, initialised with all zeros. The [math]i^{th}[/math] row in the table contains the frequency of letters in the [math]i^{th}[/math] word of the input. In another pass of the input, you can update the frequencies in the table. Now, we need to find the identical rows in the table. But comparing all pairs of rows is going to be very inefficient. So use some sort of hashing. One possible function is: Map each 26 element array of frequencies to a 26 bit integer, with [math]r^{th}[/math] bit 1 if [math]r^{th}[/math] element of the array is non-zero, and 0 if the [math]r^{th}[/math] element of the array is 0. This will map all words with same set of letters to the same integer. (They may have different frequencies of the letters.) Now for each word, only check the words that map to the same integer for anagrams.

Here is my answer in C. It gets a sentence from the user and lists the anagrams in it. #include<stdio.h>#include<string.h>void checkarray(char a[],char b[]){ if(strlen(a)==strlen(b)) { char m[strlen(a)],n[strlen(b)]; int j,k,p=0; for(j=0;j<strlen(a);j++) m[j]=n[j]='\0'; for(j=0;j<strlen(b);j++) n[j]=b[j]; for(j=0;j<strlen(a);j++) for(k=0;k<strlen(a);k++) if(a[j]==n[k]) { m[j]=1; n[k]='\0'; } for(j=0;j<strlen(a);j++) if(m[j]==1) p+=1; if(p==strlen(a)) printf("%s -- %s\n",a,b); }}int main(){ char a[200]; int i,j,m=0,n=0,ws=0; printf("Enter the sentence:\n"); gets(a); for(i=0;i<strlen(a);i++) if(a[i]==' ') ws++; char b[ws+1][20]; for(i=0;i<(ws+1);i++) for(j=0;j<20;j++) b[i][j]='\0'; for(i=0;i<strlen(a);i++) if(a[i]!=' ') b[m][n++]=a[i]; else { m++; n=0; } for(i=0;i<ws;i++) for(j=i+1;j<(ws+1);j++) checkarray(b[i],b[j]); getch(); return 0;} Output: