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 * (n1) ! , 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
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"
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.
There is further scope of optimization of this code , so any suggestions or errata are most welcome.
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 * (n1) ! , 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


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


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 subroutines 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 :)
Nice explanation
ReplyDeleteThank u very much :)
Deletenice. You permute function will run out of stack space with no return statement :)
ReplyDeleteHi user,
ReplyDeleteThanks 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
Great Job... Good Answer..
ReplyDeleteThank you Atiqur :)
DeleteThis is an awesome solution!
ReplyDeleteThanks Aravind
DeleteI enjoy what you guys are up too. This sort of clever work
ReplyDeleteand coverage! Keep up the fantastic works guys I've included you guys to my blogroll.
My site: Plantar Fasiitis Shoes
certainly like your website but you need to test the spelling on quite a few
ReplyDeleteof 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
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.
ReplyDeleteLook into my website :: how to grow taller
Aw, this was an extremely good post. Taking the time
ReplyDeleteand 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/