Python Permutations Problem

Asanka Wasala wasala at gmail.com
Fri Aug 14 12:28:34 EDT 2009


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-----------------------------------------------------------------------------



More information about the Python-list mailing list