Python Permutations Problem

[MRAB]

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