The brute force algorithm has O( n! ). However, one can take advantage of a property of anagrams which is that all anagrams have the same letters in them and can be compared for equality when you sort the letters.

Now, you're asking "How on earth can I do that with multiple words??" Well, you take advantage of another factor which is that anagrams have to have the same number of letters. So, if you want to find all words which can be made up of the letters in another word, you can restrict your search space to words whose letters add up to the right number.

So, in your example, you have a 7-letter word whose sorted letters are ACEELNS.

  1. Take all 7 letter words in the dictionary and sort them. Then, compare each one to the sorted string.
  2. Take all 6 letter words and 1 letter words. Do the same with each pairing.
  3. Take all 5 letter words and 2 letter words. Do the same.
  4. Take all 5 letter words and doubles of 1 letter words. Do the same.

Keep doing that for every combination numbers that add up to 7.

Now, this doesn't actually reduce the O() factor of the problem. Buuutt ... it does bring the actual runtime of the problem down to where modern computers can do it in reasonable time.

There are further optimizations to the algorithm, like taking advantage of letter frequencies and the like, but those are left as an exercise for the reader.

------
We are the carpenters and bricklayers of the Information Age.

Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

In reply to Re: OT: How to find anagrams? by dragonchild
in thread OT: How to find anagrams? by Cody Pendant

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.