• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

finding anagrams

 
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
given an array of say 10 words, how to display the anagrams from the list provided.

Eg: pat and tap, scared and scacred etc
 
Bartender
Posts: 10336
Hibernate Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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)
 
Vidya Ramachandran
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You could do something like this:

[ March 16, 2007: Message edited by: Garrett Rowe ]
 
Vidya Ramachandran
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
wouldnt that involve too many comparisons Garrett Rowe? is there a better solution?
 
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Vidya Ramachandran
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
thanks stan james
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic