On Aug 14, 11:28 am, Asanka Wasala <was...@gmail.com> wrote: > Hi > I am developing a spell checker for my language, and I came across > solving an interesing problem. It would be great if you can suggest > me an optimized solution for the problem described below: > > I have certain group of letters like these: > > Group #1: c,r,b > Group #2: a,z,k > Group #3: h,t > . > . > > Letters within the same group can be substituted/replaced with the > rest of the letters in that group. > > (ie. Group #1 means letter 'c' can be replaced with either 'r' or 'b', > and letter r can be replaced with either c or b, and letter b can be > replaced with either r or c) > > A group can have upto 3 letters, and letters do not overlap between > groups. There can be upto 25 such groups. > Given a word containing above letters, (e.g. 'cat'.) I want to > generate all possible words by subsituting letters in the groups. > > eg. expected output: > > cat rat bat > czt rzt bzt > ckt rkt bkt > cah rah bah > czh rzh bzh > ckh rkh bkh > > My code is given below. But for complex words like 'cccccccccczzk' it > thows the 'maximum recursion depth exceeded' error. Therefore, can you > suggest me an optimized solution to achive the above task? Thanks in > advance. > -------------------------- > CODE------------------------------------------- > #-*- coding: UTF-8 -*- > import re > def getPermutations(word): > def getSimilarLetters(letter): > pattern=u"|c,r,b|a,z,k|h,t|" > list=[] > ptrn=re.compile("(?P<grp>\|(.?,)*?"+letter+"(,.)*?\|)") > k=ptrn.search(pattern) > if k: > letterlist=k.group("grp")[1:-1] > list=letterlist.split(",") > list.remove(letter) > return list > else: > return letter > > list=[] > > def perm(word): > posi=0 > wrd=word > for w in word: > posi=posi+1 > lst=getSimilarLetters(w) > if len(lst)>0: > for l in lst: > newwrd=wrd[:posi-1]+l+wrd[posi:] > if not (newwrd in list): > list.append(newwrd) > perm(newwrd) > > try: > perm(word) > except RuntimeError: > list=[] > list.append("error") > return list > > list=getPermutations(u"cat") > > for i in list: > print i.encode('utf-8') > --------------------------------------------END of > CODE-----------------------------------------------------------------------------
IDLE 2.6.1 >>> import itertools as it >>> for i in it.product('crb','azk','ht'): print ''.join(i), cah cat czh czt ckh ckt rah rat rzh rzt rkh rkt bah bat bzh bzt bkh bkt -- http://mail.python.org/mailman/listinfo/python-list