[Python-ideas] Fwd: Extremely weird itertools.permutations

[Bruce Leban]

On Sun, Oct 13, 2013 at 1:04 PM, MRAB <python at mrabarnett.plus.com> wrote:

> Here's a use case: anagrams.
>

For what it's worth, I've written anagram-finding code, and I didn't do it
with permutations. The faster approach is to create a dictionary mapping a
canonical form of each word to a list of words, e.g.,

{
  'ACT': ['ACT', 'CAT'],
  'AET': ['ATE', 'EAT', 'ETA', 'TEA']
}

This requires extra work to build the map but you do that just once when
you read the dictionary and then every lookup is O(1) not O(len(word)).
This canonical form approach is useful for other word transformations that
are used in puzzles, e.g., words that are have the same consonants
(ignoring vowels).


--- Bruce
I'm hiring: http://www.cadencemd.com/info/jobs
Latest blog post: Alice's Puzzle Page http://www.vroospeak.com
Learn how hackers think: http://j.mp/gruyere-security

P.S. Yes, I know: if you play Scrabble, TAE is also a word.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131014/a1c25cf8/attachment.html>