Palindrome finder: help find ways to speed up?

dromedary camel at oasis.com
Wed Apr 9 18:37:23 EDT 2003


Thanks to all for the excellent suggestions. Below is a rewritten
version of the palindrome finder. My results pretty much match
Steven's. For two-word combinations, the time went from about 150
seconds to five seconds. (That's on a G4/400 running OS 10.2.4.) That's
a huge improvement. 

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.
Perhaps in another life. In this one, I'll happily accept help from
Steven or others.

_________________________________________________

##### Find all unique combinations
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):
   c=len(w)/2
   if w[:c]==w[::-1][:c]:
      print w


words = open(SOME_WORDS_DOC).read().splitlines()
i=0
dict = {}
n=2

for word in words:
   i=0
   j=1
   while i < len(word):
      if dict.has_key( word[i:][::-1] ):
         if word in dict[ word[i:][::-1] ]:   #skip if in list
            i=i+1
         else:
            dict[ word[i:][::-1] ].append(word)
            i=i+1
      else:
         dict.update( { word[i:][::-1] : [word] } )
         i=i+1
         
      if dict.has_key( word[0:j][::-1] ):
         if word in dict[ word[0:j][::-1] ]: #skip if in list
            i=i+1
         else:
            dict[ word[0:j][::-1] ].append(word)
            j=j+1 

      else:
         dict.update( {  word[0:j][::-1] : [word] } )
         j=j+1 

      
for word in words:
   if dict.has_key(word):
      if word in dict[word]:
         dict[word].remove(word) #delete repeats
      dict[word].append(word)
      combinations(dict[word], n)




More information about the Python-list mailing list