Finding all the permutations of a given
__String__ has both a **recursive solution** and a **non-recursive solution**. In
this post we'll see both kind of solutions.

**Recursive** is easy to code but a little difficult to visualize where as **non-recursive** is a little difficult to
code but once you know the logic it is easy to visualize what code is doing.

__Permutations of a String - Non Recursive__

Logic for the non recursive solution is as follows -

- First thing to do is to sort the given string in ascending order that is the first permutation so print it.
- Now we have to generate all the other permutations until the string is sorted in descending order. That becomes the last permutation to be printed and signals the end of the program.
- For every permutation previous permutation becomes the starting point and from there the steps are -
- Find the
**rightmost**char in the String which is smaller than the next character.

**As exp.**If String is BCDA then you need to scan through the chars, B is smaller than the next char 'C' but remember you have to find the rightmost character and 'C' is also smaller than the next character 'D' that means 'C' is the char you are looking for. Let's call this char as '**CHAR1**'. - Second step is to find the
**ceiling**of the '**CHAR1**' starting from the index of the '**CHAR1**', ceiling here means starting from the index of the '**CHAR1**' you have to*find the smallest character which is greater than the 'CHAR1'*. Let's call this char as '**CHAR2**'.

**As exp**. If string is BCDAE and C is 'CHAR1' then you are looking for the smallest character with in the String "DAE" which is greater than C. So it should be D so D is '**CHAR2**' in this case. **Swap**these 2 characters found using Step1 and Step2 i.e. CHAR1 and CHAR2.- In the resultant string take the substring after the index of 'CHAR1' till end and sort it.

Let's see all the steps with an example - If passed String is '**ABCDEF**' and at some point the permutation is
'**CFADEB**' then in order to find the next permutation.

In Step1 it will go through the following combinations to find the 'CHAR1' CFADEB - C-F, F-A, A-D, D-E, E-B So CHAR1 is D.

In Step2 we have to find the smallest char which is greater than D with in the substring EB. So 'CHAR2' is E.

In Step3 - Swapping these will give the String CFAEDB.

In Step 4 - if we use 0 based index then the original index of 'CHAR1' was 3. In String CFAEDB if we take the sub string after index 3 then DB is the resultant string which has to be sorted.

So the end string is **CFAEBD** and that is the next permutation.

**Note** that this logic take cares of the duplicate chars too. If you enter "DDDD" as string it will give
you only one String "DDDD" as output.

__Permutations of a String - Non-recursive Java code__

import java.util.Arrays; public class PermNR { public static void main(String[] args) { permute("ABCDEF"); } public static void permute(String str){ char[] temp = str.toCharArray(); // Step 1. Sort the string Arrays.sort(temp); System.out.println("String " + String.valueOf(temp)); int index = 0; int lowest = 0; while(true){ // Step 2. Rightmost char smallest than its neighbour for(int i = 0; i < temp.length - 1; i++){ if(temp[i] < temp[i+1]){ lowest = i; } } // index of CHAR1 index = lowest; // Step3. Find the ceiling of the int j = findCeiling(temp, index); // Breaking condition at this juncture // all permutations are printed if(j == index) break; swap(temp, index, j); String a = String.valueOf(temp); // Step4. Sort the substring char[] b = a.substring(index + 1).toCharArray(); Arrays.sort(b); a = a.substring(0, index + 1) + String.valueOf(b); temp = a.toCharArray(); System.out.println( "String " + String.valueOf(temp)); //} } } /** * * @param temp * @param index * @return */ public static int findCeiling(char[] temp, int index){ int k = index; char test = temp[index]; while (k < temp.length - 1){ if(temp[index] < temp[k + 1]){ index = k + 1; break; } k++; } k = index; while (k < temp.length - 1){ if((temp[index] > temp[k + 1]) && (temp[k + 1] > test)){ index = k + 1; } k++; } return index; } /** * Method used for swapping the char * @param str * @param i * @param j */ private static void swap(char[] str, int i, int j){ char temp = str[i]; str[i] = str[j]; str[j] = temp; } }

__Permutations of a String - Recursive__

Here the method will call itself, keeping portion of a string as constant. A base condition is also needed which is when string length is 0.

public class PermDemo { public static void main(String[] args) { permutation("abcde"); } public static void permutation(String str) { permutation("", str); } // recursive method private static void permutation(String prefix, String str) { int n = str.length(); if (n == 0){ System.out.println(prefix); } else { for (int i = 0; i < n; i++){ //System.out.println("prefix " + prefix + " i " + i); permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); } } } }

Source for recursive code is : http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html

__Explanation__

After first base point when n becomes 0 we'll have these 3 calls. Note that for all these calls i will be 0 as permutation method is called again.

permutation("a", "bc"); permutation("ab", "c"); permutation("abc", "");

Since method calls follow stack data structure so FIFO (First In First Out) will be followed. Let's lay out our method calls in that way.

permutation("abc", ""); permutation("ab", "c"); permutation("a", "bc");

Now first call will print the String "abc", second call permutation("ab", "c") will go in the for loop with i = 1 and n = 1 so it will come out and won’t print anything as for loop has condition (i < n). Third call permutation(“a”, “bc”); will go in the for loop with i =1 and n=2. Which will lead to following calls again following that same pattern as explained above it will print acb.

Permutation("a", "bc"); Permutation("ac", "b"); Permutation("acb", "");

That's all for this topic **How to find all the permutations of the given String**. If you have any doubt or any
suggestions to make please drop a comment. Thanks!

__Related Topics__

**You may also like - **

## No comments:

## Post a Comment