Friday, January 12, 2007

[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
for key,value in d.items():
if value == 0:
# 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..

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