On May 4, 2:04 am, "Gabriel Genellina" <[EMAIL PROTECTED]> wrote:
> En Sun, 04 May 2008 02:17:07 -0300, dave <[EMAIL PROTECTED]> escribió:
>
>
>
> > Hello,
>
> > I made a function that takes a word list (one word per line, text file)
> > and searches for all the words in the list that are 'shifts' of
> > eachother. 'abc' shifted 1 is 'bcd'
>
> > Please take a look and tell me if this is a viable solution.
>
> > def shift(word, amt):
> > ans = ''
> > for letter in word:
> > ans = ans + chr((ord(letter) - ord('a') + amt) % 26 + ord('a'))
> > return ans
>
> > def fileshift(x):
> > fin = open(x)
> > d = {}
> > for line in fin:
> > d[line.strip()] = [1]
> > for i in range(1, 26):
> > ite = shift(line.strip(), i)
> > if ite in d:
> > print ite
>
> > Any tips/suggestions/critiques greatly appreciated.. I'm trying to
> > teach myself Python (and still beginning) and would love any helpful
> > info.
>
> First, looking at the code, you're evaluating line.strip() a lot of times;
> I'd avoid it.
> Looks like you're using a dictionary just for the keys - the set type is more
> adequate here (seehttp://docs.python.org/lib/types-set.html). In any case,
> I'd use a value like None instead of [1]
> But I'd use a different algorithm. Instead of generating all posible shifts
> for a given word, I'd substract the newly read word from each previous words
> (here, "substract two words" means substract the character code for
> corresponding positions, modulo 26). Shifted words, when substracted, have
> the same number on all positions.
A faster algorithm is to create a 'key' for each word, defined as the
tuple of ord differences (modulo 26) of consecutive characters. E.g.
the key of 'acf' is (2,3); 'c' is 2 positions after 'a' and 'f' 3
positions after 'c'. Shifted words (and only these) have the same key.
Here's a straightforward implementation that generates all the lists
of equally-shifted words:
from collections import defaultdict
def iter_shifted(words):
key2shifted = defaultdict(list)
for word in words:
ords = map(ord,word)
key = tuple((ords[i]-ords[i-1]) % 26
for i in xrange(1,len(ords)))
key2shifted[key].append(word)
for shifted in key2shifted.itervalues():
if len(shifted) > 1:
yield shifted
if __name__ == '__main__':
words = 'abc bef jas cba cde zab azy hkl'.split()
for shifted in iter_shifted(words):
print shifted
# *** output ***
#['bef', 'hkl']
#['abc', 'cde', 'zab']
#['cba', 'azy']
--
http://mail.python.org/mailman/listinfo/python-list
