Thread: Words in a Word

  1. #1
    Registered User
    Join Date
    Jun 2011

    Words in a Word

    Hello! I am stuck and I was hoping someone here could help me. I have this text file of around 55000 words. What I want to do is find, for each word, as much words as can possibly be made by deleting or arranging the letters in that word.

    A solution I was thinking is to parse the string and assign each letter to a char variable. Then arrange these characters in every possible way and compare the newly created words to my database to see if they exist. My problem is I do not know how to arrange these letters in every possible way. How can you do this? and if you have another solution please feel free to tell me.

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Anagram detection is usually done by converting the things to be compared into a form that is ignorant of the letter ordering. One way to do this is by simply rearranging the letters into a single standard form, e.g. by sorting them. If two words have the same standard form, they are anagrams.

    You also take your database and preprocess it by building a map from each standard form to all the words that reduce to it.

    Finding every possible rearrangement is far too slow. We're talking about heat death of the universe too slow.

    Deleting characters is also done on the standard form. When deleting from the standard form, be sure to skip redundant deletions, e.g. the standard form of anagram is aaagmnr - there's no difference in which a you delete, so only do it once. It may help you to use a standard form that encodes letters just once, remembering their count, i.e. the standard form becomes 3a1g1m1n1r.
    Last edited by CornedBee; 06-14-2011 at 05:29 AM.
    All the buzzt!

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    Jun 2011
    Thanks CornedBee! Using anagrams seems to be a much better idea. Let me look into it and I'll post if something goes wrong.

    Thanks again

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 04-27-2011, 10:56 PM
  2. Replies: 7
    Last Post: 10-01-2010, 04:09 PM
  3. Reading words and analyzing words from file
    By desmond5 in forum C Programming
    Replies: 7
    Last Post: 02-26-2008, 03:51 PM
  4. Replies: 5
    Last Post: 09-28-2004, 12:38 PM
  5. open file, search of word, replace word with another
    By Unregistered in forum C++ Programming
    Replies: 0
    Last Post: 06-05-2002, 01:16 PM