Sep 29, 2009

Playing with recursion - string permutation

I have always had this feeling that I did not have a better hang of the concept of recursion. I know I could easily write recursive functions like computing factorial, Fibonacci series etc using recursion but when it really comes down to something outside of the norm I will instantly get this queasy feeling. So, to put an end to this, I started learning recursion and to demonstrate my learning I have put together a simple recursive function to compute the different permutations of a string with distinct characters. Given an input string, this function will emit all possible permutations of the supplied string by re-arranging the characters inside the string. Let us begin by analyzing how we would solve this problem on paper.

First, let us have a look at few sample strings and their permutations.

Input String: 'ab'
Permutations: 'ab', 'ba'

Input String: 'abc'
Permutations: 'abc', 'acb', 'bac', 'bca', 'cab', 'cba'

Input String: 'abcd'
Permutations: a + all permutations of 'bcd', b + all permutations of 'acd', c + all permutations of 'abd', d + all permutations of 'abc'

As soon as we reached a 4 characters string the permutations become unwieldy and is becoming a challenge to compute mentally. However, if we recall from our math class, we know that we can have a maximum of 4! (factorial) permutations with a 4 characters string equaling 24 different variations.

But this simple analysis has given out the solution for us. If you look closely you will notice that for a string with 4 characters, we were computing permutations by combining each character from the 4 characters string with the result of all possible permutations of the remaining string with 3 characters. Similarly for the string with 3 characters we can compute the permutations by combining each characters of the 3 characters string with the result of all possible permutations of the remaining string with 2 characters and so on.

permutation ('abcd') = a + permutation('bcd') and so on
permutation('bcd') = b + permutation('cd') and so on
permutation('cd') = c + permutation('b') and so on
permutation('b) = b (Since there is nothing to permute with just one character)

The above flow lends itself elegantly to a recursive solution. I have specified the pseudo code below.

permutation(string)
{
 myList = empty

 if string.length == 1
  Add string to myList
 else
  for each char in string
   for each permutation(string-char)
    Add char + permutation to myList
 return myList
} 

Note the recursive call to "permutation" inside the function. Find below the implementation in Python.

def permute(instr):
 myList = list()
 if len(instr) == 1:
  myList.append(instr)
 else:
  for inchar in instr:
   for perm in permute(redux(instr, inchar)):
    myList.append(inchar + perm)
 return myList


def redux(instr, inchar):
 outstr = ''
 for c in instr:
  if c != inchar:
   outstr += c
 return outstr

I am a newbie to Python. Therefore, you may find code above that may not be the norm among pycoders.
Also, be warned, the above implementation & logic works only for string with distinct characters. If you have repetitive characters, the above logic will produce erroneous results.

1 comment: