Palindrome finder: help find ways to speed up?

[Steven Taschuk]

Quoth dromedary:
> I've written a palidrome finder two ways (see below), both of which
> work, but verrrrrry slooooooooooowly. Would anybody out there care to
> look over the code and offer an idea or two about how to speed it up?
  [...]

Your approach to the problem is inherently slow, I think.  You go
through all combinations of k words from your word list, and check
each for palindromicity.  That's (n choose k) * k! combinations
checked.

A smarter search would do better.  One approach would be to build
the palindrome from both ends instead of from just one end.  For
example, suppose your code understood that a palindrome starting
with 'orange' must end with a word 'o', 'ro', 'aro', 'naro',
'gnaro', 'egnaro', or a word ending with 'egnaro'.  If there are
no such words, it can skip 1/n of the search space, namely all the
combinations which start with 'orange'.

-- 
Steven Taschuk             "The world will end if you get this wrong."
staschuk at telusplanet.net     -- "Typesetting Mathematics -- User's Guide",
                                 Brian Kernighan and Lorrinda Cherry