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
