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

- get all the unique characters in a pool of pairs, each pair (symbol, no_of_occurances)
- consider each permutation as a set of n blanks, n = strlen(given string)
- for each position/blank in the permutations,
- 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. - now we go down the line to the next blank and repeat 3 //this is a recursive step..
- 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 ..

- we pick a symbol to go into that blank.. In picking, we reduce the number of occurance..

## No comments:

Post a Comment