14 Oct 2013

Permutation of a String

Problem Statement :
    Print all the permutation of a given String.

Solution:

       Permutation in mathematics for n items take together at a time is  n!
We also know that  n! = n * (n-1) ! , which clearly gives an intuition that this problem can be solved using recursion.

Here the concept is to fix the 1st character , and generate permutation of the rest , then fix two characters and generate permutations of the rest , repeat this technique until all characters are processed. 
Supposing we have characters 'a' , ' b ' , ' c ' , ' d ' and we have to find permutation the given characters, so our approach will be as follows :

                   fix ' a ' followed by permutations of  ' b ' , ' c ' , ' d ' .
Similarly,   fix ' b ' followed by permutations of  ' a ' , ' c ' , ' d ' .
Similarly,   fix ' c ' followed by permutations of  ' a ' , ' b ' , ' d ' .
Similarly,   fix ' d ' followed by permutations of  ' a ' , ' b ' , ' c ' .

For e.g. permutation of "ABCD" are

                      

ABCD
BACD
CBAD
DBCA
ABDC
BADC
CBDA
DBAC
ACBD
BCAD
CABD
DCBA
ACDB
BCDA
CADB
DCAB
ADCB
BDCA
CDAB
DACB
ADBC
BDAC
CDBA
DABC



















In order to avoid repetition of  swapping of characters in case of duplicates , we are checking if the character is  in the range of indexes among which swapping is happening ,  if any character is found then we skip the current characters as that same character in that range will be processed at some later time during iteration , hence the match(int i , int j) subroutine helps to check the above condition.

Therefore in case of duplicate charaters in the string.
e.g. "AACD"



AACD
ACDA
CAAD
DACA

AADC
ADCA
CADA
DAAC

ACAD
ADAC
CDAA
DCAA












Lets get on to the ground level. How are we gonna implement this ?? What would we require , loops , function calls or what other necessary things ?? before proceeding to write the code.
 We would implement the above logic by fixing every character at 1st position so we would obviously require a for loop running till the number of charaters in the String. Fixing a character at a position we repeat the process for the rest of characters by incrementing the start index , this process would be repeated until the start index has reached the length of the string , then we would print the string. This is just an overview to give an idea to proceed before you start coding.

Full Source Code:  LINK

Important sub-routines necessary for calculating permutations are shown below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
         private char[] str=null; // to hold string data
 /**
  * Subroutine to compute permutations
  * @param index
  * @param len
  */
 private void permutate( int index, int len )
 {
  if( index == len )
   System.out.println((str));

  for(int i = index; i <= len; i++ )
  {
   if(!match(index, i)){ 
   swap(index, i ); 
   permutate(index + 1 , len);
   swap( index, i );   
   }
  }
 }

 /**
  * to check if any character matches between i and j
  * @return if any characted match found
  */
 private  boolean match(int i, int j) {
  if(i == j) 
   return false;
  else
   for(;i<j ; i++)
    if(str[i]==str[j])
     return true;
  return false;
 }


There is further scope of optimization of this code ,  so any suggestions or errata are most welcome.
Happy Coding  :)

12 comments:

  1. Nice explanation

    ReplyDelete
  2. nice. You permute function will run out of stack space with no return statement :)

    ReplyDelete
  3. Hi user,
    Thanks for commenting , it wont , it is checking for the possible combinations in set , the size of the set is increasing with the for loop, please check the code with the implementation. Pls do write back.
    Link : http://ideone.com/F9eCcr

    ReplyDelete
  4. I enjoy what you guys are up too. This sort of clever work
    and coverage! Keep up the fantastic works guys I've included you guys to my blogroll.


    My site: Plantar Fasiitis Shoes

    ReplyDelete
  5. certainly like your website but you need to test the spelling on quite a few
    of your posts. A number of them are rife with spelling problems and I in finding it very troublesome to tell the truth nevertheless I'll
    surely come back again.

    My site: how to grow taller

    ReplyDelete
  6. Its not my first time to pay a visit this web site, i am visiting this web page dailly and obtain nice information from here all the time.


    Look into my website :: how to grow taller

    ReplyDelete
  7. Aw, this was an extremely good post. Taking the time
    and actual effort to make a really good article… but what can I say… I put
    things off a whole lot and don't seem to get nearly anything done.


    Look into my website ... http://nouveauclashofclanstriche.blogspot.com/

    ReplyDelete