Python Permutations Problem

[Mensanator]

On Aug 14, 11:28 am, Asanka Wasala <was... at 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