Print permutation of a string
  • recursion
  • character
  • string
  • permutation
  •   
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2404)

How will you design an algorithm to print all permutation of a String?


Posted Answers

We can find the permutation of a string by using recursion.


  • Take the first character of the input string.
  • Permute all the characters in the remainder of the string recursively and create a new array with them.
  • Add the first character into each possible position of the new array and return.


Example - Let the input string be 'amy'. After taking the first character \( a \) the remainder is 'my'. Permuting the remainder the new array becomes ['my','ym']. Adding \( a \) in the new array, the result becomes [\( \underbrace{amy,may,mya}_{in \ 'my'} \), \( \underbrace{aym,yam,yma}_{in \ 'ym'} \)].

Time complexity = \( O(n!) \).

public static ArrayList   computePermutations(String string){

List perm = new ArrayList ();

/* Check the input string */
if(string.length == 0)
perm.add("");
return perm;

/* Take the first character of the string */
char firstLetter = string.charAt(0);
/* Remainder of the string */
String remainder = string.substring(1);
ArrayList word = computePermutations(remainder);

/* Iterate through the new array */
for(String index : word){
/* Length of each element in the array */
for(int j = 0; j < =index.length; j++)
perm.add(insertCharacter(index, firstLetter, j));

}
/* return the result */
return perm;
}

// This function inserts letter 'char' in 'string' before 'i'
public int insertCharacter(String string, char char, int i){
/* Get the substring from 0 to i-1 */
String begin = string.substring(0, i);
/* Get the substring from i to end */
String end = string.substring(i);
/* Put the letter in between i-1 and i */
return begin + char + end;
}

You need to Sign In to post your solution.