Algorithm to find Permutations of String using Recursion

Find Permutation and Combination of a String , such type of questions can be asked in the written round of the major tech giants like Amazon. There are many ways we can find the permutation of the String , one we already discussed using anagram solver technique. 

Read Also :   Find Permutation of String using Anagram Solver Logic

Let us understand first , what we want to achieve . We want to write a function which prints all possible orderings of the characters in the string, in other words, print all permutations that use all the characters from the original string.
For example , given a string "sky" , our function should return

Output :  "ysk","ksy","yks","kys","syk" and "sky"

What if there are repeated character in the string .Simply, we need to keep one thing in mind, just treat each character in the input string as a distinct character, even if it is repeated.
For example , given a string "ooo" , our function should print



Output :  print six times "ooo" 


To find how many permutations can be created from 'n' number of alphabets in the original string is given by :  n!
So in above examples number of alphabets  in the original string is 3 , thus possible permutations are 6 .

Logic 

For each letter that we choose for the first(leftmost) position,we need to write all the permutations beginning with that letter before we change the first letter. Likewise, if we pick up a letter for the second position , we need to write out all permutations beginning  with this two letter sequence before changing the letters in either the first or second position.
In other words , we can define the permutation process as picking a letter for a given position and performing the permutation process starting at the next position to the right before coming back to change the letter we just picked.

As each letter from the input string can appear only once in each permutations, "all allowable characters"  cant be defined as every letter in the input string. "All allowable character" means all letters in the input string that haven't already been chosen for a position to the left of the current position (a position less than n). We need to check this scenario algorithmically . We can check each candidate letter for a position n against all the letters in positions  less than n to determine whether it had been used. We can eliminate these inefficient scans by maintaining an array of boolean values corresponding to the positions of the letters in the input string and using this array  to mark letter as used or unused, as appropriate.


Read Also :     Count number of words in the String : Code with Example

Pseudo Code 

1.  If we have past the last position
          Print the String
          Return
2.  Otherwise
          For each letter in the input string        
          If its marked as used, skip to the next letter
          Else, place the letter in the current position
                 Mark the letter as used
                 Permute remaining letters starting at current pos. + 1
                 Mark the letter as unused  

Read Also :    Remove Specific Characters from the String : Java Source Code with Example


Java Source Code :

public class Permutations {
    private boolean[] used;
    private StringBuilder out = new StringBuilder();
    private final String in;
    public Permutations( final String str ){
        in = str;
        used = new boolean[ in.length() ];
    }
    public void permute( ){
        if( out.length() == in.length() ){
            System.out.println( out );
            return;
        }
        for( int i = 0; i < in.length(); ++i ){
            if( used[i] ) continue;
            out.append( in.charAt(i) );
            used[i] = true;
            permute();
            used[i] = false;
            out.setLength( out.length() - 1 );
        }
    }
}

Please write in comments in case you have any doubts