File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Java in General and the fly likes finding anagrams Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "finding anagrams" Watch "finding anagrams" New topic

finding anagrams

Vidya Ramachandran

Joined: Nov 04, 2005
Posts: 24
given an array of say 10 words, how to display the anagrams from the list provided.

Eg: pat and tap, scared and scacred etc
Paul Sturrock

Joined: Apr 14, 2004
Posts: 10336

The hard part of this is how to infom your program what constitutes a valid English word. What you need is some sort of dictionary resource to supply your list of valid words. Have a google for Java spell checkers. These always have such a thing.

(Note: Your second example is not an anagram)

JavaRanch FAQ HowToAskQuestionsOnJavaRanch
Vidya Ramachandran

Joined: Nov 04, 2005
Posts: 24
thanks for your response paul. in the second example, i meant scared and sacred..sorry about the typo! i have figured out a method to find anagrams. first we alphabetically sort each word in the list. then we sort the list itself so that anagrams are together. but then how to establish which jumbled word corresponds to the original word? can some please help me to code this.

eg : original list :- scared,take,pack,sacred,pat,tap
sorting each word gives :- acders,aekt,ackp,acedrs,apt,apt
sorting the list gives :- acders,acders,ackp,aekt,apt,apt
how to establish that the two acedrs gives scared and scared. also the two apt corresponds to pat and tap
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
You could do something like this:

[ March 16, 2007: Message edited by: Garrett Rowe ]

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Vidya Ramachandran

Joined: Nov 04, 2005
Posts: 24
wouldnt that involve too many comparisons Garrett Rowe? is there a better solution?
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Maybe a "multi map" ... Work through the input list and make a Map with key = sorted value and value is a List of words that give the same sorted result. (We already know they are anagrams of each other.)

Key = acders
Value = List { sacred, scared }

Then you can sort each dictionary word and see if it's in the map.

I'd be tempted to take a totally different approach ... use recursion to try all possible shufflings of the letters in each input word, compare those to valid words in the dictionary. A Ternary Search Tree could make the dictionary search very fast and you could check each letter as you go as part of the recursive routine. If that made no sense at all, please stick with what you have.

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Vidya Ramachandran

Joined: Nov 04, 2005
Posts: 24
thanks stan james
I agree. Here's the link:
subject: finding anagrams
It's not a secret anymore!