Palindrome finder: help find ways to speed up?

[Steven Taschuk]

Quoth Jon Brown:
> Actually the program does exactly what you describe, except from the inside
> out because it starts in the middle, and it cuts out of the loop if the
> characters don't match.

I see that I haven't expressed clearly what I'm suggesting.

The combinations() function recursively produces *all* k-lists of
words from the word list, whether or not it can be determined
partway through the assembly that no possible palindrome starts
with the list assembled thus far.  For example, if you ask for all
4-word-long palindromes given a word list of 6 words, it makes 360
= (6 choose 4)*4! calls to rPal().

My suggestion is that, if the word list is, say,
	abandon
	major
	wombat
	articulate
	orange
	royal
then the program could start with 'abandon', notice that no word
in the word list ends with 'a', and immediately, er, abandon
trying to find palindromes starting with this word, and move on to
finding palindromes starting with 'major'.  The code as it stands
does not make this inference, and so unnecessarily generates the
(5 choose 3)*3! = 60 sequences of 4 words which start with
'abandon', and tests them individually for palindromicity.

> To look for pals it spins off big, big numbers of combinations, true enough.
> That's what behind the need for speed. Since Python is inherently on the
> pokey side, I expected the slowness but wonder if I'm missing a cool way to
> pick up the pace. But I suspect the solution will involve C++, and I've
> never linked C/C++ with Python.

Going to C might yield some improvement, but it will do nothing to
deal with the combinatoric explosion which is in my opinion the
real performance sink in this problem.

-- 
Steven Taschuk                               staschuk at telusplanet.net
"What I find most baffling about that song is that it was not a hit."
                                          -- Tony Dylan Davis (CKUA)