[Python] Permutations of a string

[This post has been translocated from my python blog to this blog, as I'm planning to close down my python blog.. It's not seeing much attention from me anyways :D ]

Given a string of any length, this python program generates all permutations of the characters in the string. The program is capable of taking care of repeated occurrences of the same character

count = 0  # a global counter to give a unique id to each permutation
        # that is generated


def constructDict (s):
 """Constructs the dictionary.

 Constructs the dictionary of
 unique character to no-of-occurance mapping.
 """
 d = {}
 for i in range(0,len(s)):
     try:                           # if the character is already present
         d[s[i]] = d[s[i]] + 1      # increment its count
     except:                        # if the character is not already presetn
         d[s[i]] = 1                # put it in and set its count as 1
 return d


def recursivePermuter ( d, strSoFar, maxDepth, thisDepth = 0 ):
 """Constructs all permutations.

 d: the dictionary
 strSoFar: the prefix part of the string which
           has been constructed so far
 maxDepth: this is same as the length of the
           user input string
 thisDepth: this level of recursion (Default value 0)

 Each place in the permutation can be occupied by
 an "available" character. An "available" character is
 one whose value in the dictionary d is not zero.
 When we use/borrow an available character, we decrement
 its value in the dictionary; and when we backtrace/return
 the available character, we restore its value by
 incrementing once.
 """
 global count
 if (thisDepth == maxDepth):         # if we have completed one permutation
     count = count + 1
     print str(count) + ": " + strSoFar
     return
 for key,value in d.items():
     if value == 0:
         continue
     # all elements in d with value > 0 are "candidates" to go
     # into this place.. We give each a chance systematically..
     d[key] = value - 1
     recursivePermuter ( d, strSoFar + key, maxDepth, thisDepth + 1 )
     d[key] = value


def __main__ ():
 """The perpetrator of all evil.
 """
 s = raw_input("Enter String: ")     # get the user input string
 d = constructDict(s)                # construct the dictionary
 recursivePermuter(d, "", len(s))    # despatch to the guy
                                     # who churns out permutations


# you have to explicitly call the main
# main, in python is a convention rather than
# a mandate..
__main__()

How it works..

1. get all the unique characters in a pool of pairs, each pair (symbol, no_of_occurances)
   
2. consider each permutation as a set of n blanks, n = strlen(given string)
   
3. for each position/blank in the permutations,
   
   
   
   1. we pick a symbol to go into that blank.. In picking, we reduce the number of occurance..
      So obviously also note that we may not pick a symbol whose number of occurances is already zero.
      
   2. now we go down the line to the next blank and repeat 3 //this is a recursive step..
      
   3. once the recursive function returns, we return the symbol we had borrowed for this instance
      of the recursive function.. We do so, by incrementing the number of occurances by one ..