[Tutor] Algorithm

[Kent Johnson]

On Sun, Aug 23, 2009 at 6:06 PM, kreglet<kreglet at gmail.com> wrote:
>
> Hello,
>
>  The problem that I am having is writing an algorithm for finding all the
> possible words from a given word. For example: python
>
> from "python" you can make the words pot, top, hop, not etc. There are few
> examples for making anagrams for a word, but only the whole word. I have
> tried unsuccessfully to modify some of these to suit my purpose. Also on the
> web there are numerous sites where you can type in a word and it will give
> you a list of all the words that could be made from it. How would I go about
> this in python?

Another way to do this:
- sort the letters in the target word; for example 'python' becomes 'hnopty'
- sort the letters in the word you want to test, for example 'pot' becomes 'opt'
- walk through test letters looking for them in the target list. For
each test letter,
  - if it matches the current target letter, go to the next letter in each list
  - if it is less than the current target letter, go to the next target letter
  - if the test letter is greater than the target letter, or you run
out of target letters, there is no match
  - if you get to the end of the test letters, you have a match

The code for this is pretty simple and doesn't require much in the way
of data, just the two lists of letters. If you like I can share my
implementation.

Kent