# Palindrome finder: help find ways to speed up?

dromedary camel at oasis.com
Tue Apr 8 18:30:50 CEST 2003

```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?

The first example uses recursion (handy for combining any number of
words); the second example uses for loops (not fast but faster, though
clunkier).

But‹if you suggest a C/C++ wrapper or extension, please please give me
guidance on how to implement it. I've never translated a Python widget
into C/C++.

___________________________________________________

CODE 1 (uses recursion to combine words, then looks for palindromes)

##### Combine 'em
def combinations(alist, numb, blist=[]):
if not numb:
return rPal(''.join(blist))
for i in range(len(alist)):
blist.append(alist.pop(i))
combinations(alist, numb-1, blist)
alist.insert(i, blist.pop())

##### Look for symmetry
def rPal(w):
x=0
y=1
L=len(w)
h=L/2
if L % 2 > 0:
while x < h:
if w[h-y]==w[h+y]:
x=x+1
y=y+1
if x == h:
print w
break
else:
break
else:
while x < h:
if w[h-y]==w[h+x]:
x=x+1
y=y+1
if x == h:
print w
break
else:
break

##### Get a word list

##### Set number of words to combine
n=SOME_NUMBER_OF_WORDS

########################################
##### Call the recursive function to print the palindromes
if __name__ == '__main__':

combinations(words, n)

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

CODE 2 (for loops; the example uses three loops, but you can see how
complex it can get for each additional iteration)

##### Get a word list

##### Combine pairs of words into keys and values
for i in words:
for j in words:
for k in words:
if i != j and i != k and j !=k:
w=i+j+k
x=0
y=1
L=len(w)
h=L/2
if L % 2 > 0:
while x < h:
if w[h-y]==w[h+y]:
x=x+1
y=y+1
if x == h:
print w
break
else:
break

else:
while x < h:
if w[h-y]==w[h+x]:
x=x+1
y=y+1
if x == h:
print w
break
else:
break

```