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

Reply via email to