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