Java program to find all the permutations of a given String can be written using both recursive and non-recursive methods. 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.
Java program for finding 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.
For example, 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.
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));
//}
}
}
/**
*
*/
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
*/
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 Java code
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 LIFO (Last 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 Find All Permutations of a Given String Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
method calls follow stack data structure LIFO(Last In First Out) not FIFO(First In First Out).
ReplyDelete