Palindrome finder: help find ways to speed up?

[Steven Taschuk]

Quoth dromedary:
  [...]
> And if I were less a dunderhead, I'd see how to generalize to
> combinations above n=2. Times like this I wish I'd studied math or CS.

You've made a good start.  If I understand correctly, your
variable 'dict' (which, btw, could use a different name -- 'dict'
is a built-in) holds a map from 'foo' to a list of words starting
or ending with 'oof'.  Thus, you only try to find two-word
palindromes using pairs of words such that the second contains the
first reversed, which much reduces the search space.  Quite a win.

The code skips combinations in which the first word occurs
reversed in the middle of the second; this is not important for
two-word palindromes, of course.  For larger palindromes one might
imagine making a dict which maps from strings to words in which
those strings occur anywhere as a substring... at least you'd be
able to say your code has a big dict.

But there's something better.  If the palindrome is to start with
'foo', we already know where the word ending with 'oof' has to go:
at the end of the phrase.  So we can construct a phrase with a gap:
    foo ... aloof
This is partway towards a palindrome: the leading 'foo' matches
the trailing 'oof'.  We also know that it needs a word after
'foo', a word which starts with 'la', to match the unmatched 'al'
of 'aloof'.  Supposing the word list contains 'latent', we can
build
    foo latent ... aloof .
Now we need 'tnet' on the right.  Note that we want to be able to
find the word 'net' here; that is, we have to look not just for
words ending with 'tnet', but also for the complete words 'net',
'et', and 't'.  Such words would partially match what we're trying
to match, and we'd continue trying to add words to the same side
as before.  With 'net', in fact,
    foo latent net aloof
is a palindrome, because the 't' of 'tnet' which 'net' doesn't
match can match itself.  The search can continue from
    foo latent ... net aloof ,
seeking words ending with 't', to find such things as
    foo latent endorse tar rates rod net net aloof .

This approach is illustrated in detail by the following trace from
a slightly hacked version of the aforementioned code.  It's doing
a depth-first search looking for palindromes of up to seven words,
using words from ['is', 'it', 'no', 'one', 'open', 'position'].
Parentheses indicate letters whose mirror image has not yet been
put in the palindrome being built.

  "(is) ... "
  "(it) ... "
  "(no) ... "
   -  "no ... (positi)on"
   -   -  "no it ... (posi)tion"
   -   -   -  "no it is ... (po)sition"
   -   -   -   -  "no it is op(en) ... position"
   -   -   -   -   -  "no it is open ... (o)ne position"
                              palindrome: no it is open one position
   -   -   -   -   -   -  "no it is open o(ne) ... one position"
   -   -   -   -   -   -  "no it is open o(pen) ... one position"
  "(one) ... "
   -  "on(e) ... no"                              palindrome: one no
   -   -  "one ... (on)e no"
   -   -   -  "one no ... one no"          palindrome: one no one no
   -   -   -   -  "one no ... (one) one no"
   -   -   -   -  "one no ... (open) one no"
   -   -   -   -  "one no ... (position) one no"
   -   -   -   -   -  "one no no ... (positi)on one no"
   -   -   -   -   -   -  "one no no it ... (posi)tion one no"
   -   -   -   -  "one no ... (no) one no"
   -   -   -   -   -  "one no on(e) ... no one no"
                                    palindrome: one no one no one no
   -   -   -   -   -   -  "one no one ... (on)e no one no"
   -   -   -   -  "one no ... (is) one no"
   -   -   -   -  "one no ... (it) one no"
  "(open) ... "
  "(position) ... "

Note that this search strategy has no need for the combinations()
function; the right order of words is found by construction.

-- 
Steven Taschuk              Aral: "Confusion to the enemy, boy."
staschuk at telusplanet.net    Mark: "Turn-about is fair play, sir."
                             -- _Mirror Dance_, Lois McMaster Bujold