### 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: 5 years ago Updated: 5 years ago 0 0 Edit 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; }