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----------------------------------------------------------------------------- -- http://mail.python.org/mailman/listinfo/python-list