Asanka Wasala 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.
--------------------------
[snip]
This uses a generator in order:
def get_permutations(word, group_dict):
if word:
for first in group_dict[word[0]]:
for rest in get_permutations(word[1 : ], group_dict):
yield first + rest
else:
yield ""
def count_permutations(word, group_dict):
if word:
total = 1
for letter in word:
total *= len(group_dict[letter])
return total
else:
return 0
group_def = u"crb azk ht"
group_dict = {}
for group in group_def.split():
for letter in group:
group_dict[letter] = group
word = u"cat"
print "There are %d permutations." % count_permutations(word, group_dict)
print
for perm in get_permutations(word, group_dict):
print perm
--
http://mail.python.org/mailman/listinfo/python-list
