words within a word

[toefraz]

Hi all. I've been given an assignment to construct an algorithm that can find all words that occur within a given word. For example:

Given furthermore, solutions could be
form,
the,
further,
more,
theme
...and so on.

I thought about using the STL next_permutation() function, but it only finds permutation with the same amount of letters. Searching the dictionary for correct words isn't hard, I just can't start to figure out how to come up with all of the words. Any suggestions?

[newb16]

something like this

foreach( word in dictionary)
{
 foreach ( letter in [A..Z] )
 {
  if( letter_count(word, letter)>letter_count(original_word, letter) )
   next word;
 }
 print word;
} 
 

ie if each letter occurs the same or less times in dictionay word that original word, it can be constructed from the letters of original word.
Calculation of letter_count(original_word,letter) probably should be moved outside the loop because is has the same value for any word_in_dictionary.

[toefraz]

I looked at that algorithm, but it requires looking at each word in the dictionary, and then seeing if it can be made from the given word, and is a very slow algorithm (takes about 15seconds on my core 2 duo 2ghz!) I know the faster way would be to find all combinations of the given word and matching them against the dictionary because then you wouldn't have to check every single dictionary entry. I just can't figure out how to do the combinatorial algebra to divine each combination.

[Banfa]

Try one on paper, for instance try finding the all the combinations available from 5 letters (A, B, C, D, E).

Do it by the number of combinations for each result length so find the number of combinations of length 1, then length 2 and 3, 4 and 5.

Look at how you did it and then try to duplicate it on your computer as an algorithm.

Be aware that if you have 2 letters the same in the initial word you risk producing some duplicate results. That is if the word is "free" and you are picking 2 letter combinations then there are 2 ways of picking both "fe" and "re".

You could also try look up the maths for combinations which is binomial coefficients.

[arnaudk]

Once you have the various permutations, you'll need to check if they're actual words. For an efficient way of doing this, check out this thread.

[donbock]

I looked at that algorithm, but it requires looking at each word in the dictionary, and then seeing if it can be made from the given word, and is a very slow algorithm (takes about 15seconds on my core 2 duo 2ghz!) I know the faster way would be to find all combinations of the given word and matching them against the dictionary because then you wouldn't have to check every single dictionary entry. I just can't figure out how to do the combinatorial algebra to divine each combination.

You may be disappointed by that strategy. Take your example: "furthermore". Your strategy requires you to first compose a list of all the 1-letter sequences, 2-letter sequences, ... and finally the 11-letter sequences that can be formed from those 11 letters and then check each against your dictionary to see if it is a word.

Notice that I said "sequence" rather than your term "combination". That's because "combination" is a technical term in this context. You should look up the terms "permutation" and "combination" to see which is appropriate for your problem. If you're not already familiar with it, you should also look up the "factorial" operator.

For an 11-letter word, there are 108,303,111 different sequences to compare against your dictionary! Odds are that's a lot more terms than are in your dictionary. This number comes from trusting the combination/permutation function in Excel.

A lot of times the best way to start a coding problem is to NOT code ... but think about the strategies you might use and then find ways to compare them.

Cheers,
donbock

[donbock]

something like this

foreach( word in dictionary)
{
 foreach ( letter in [A..Z] )
 {
  if( letter_count(word, letter)>letter_count(original_word, letter) )
   next word;
 }
 print word;
} 
 

ie if each letter occurs the same or less times in dictionay word that original word, it can be constructed from the letters of original word.
Calculation of letter_count(original_word,letter) probably should be moved outside the loop because is has the same value for any word_in_dictionary.

Another approach would be to sort the letters in the original word and then, for each dictionary word, compare the sorted original word against the sorted dictionary word. This is similar to Knuth's anagram algorithm in "Sorting and Searching". Notice that unlike Knuth, you are not seeking equality in this comparison. Presorting the dictionary would be a very good tactic if several input words were to be checked.

Cheers,
donbock