Java Program to Find All the Permutations of a String

One fascinating problem in the world of strings is the generation of permutations. In essence, a permutation of a string is any arrangement of its characters in a different sequence. For instance, the permutations of the string "abc" are "abc", "acb", "bac", "bca", "cab", and "cba". In this article, we will write a Java program that generates all permutations of a given string.

The Strategy

• We'll approach this problem recursively.
• Choose each character as a starting character and find permutations of the remaining characters.
• Recursively repeat the process for the remaining characters until no characters are left.

Java Program to Find All the Permutations of a String

``````public class StringPermutations {

public static void main(String[] args) {
String input = "abc";
generatePermutations(input, "");
System.out.println("All permutations of " + input + " have been displayed.");
}

public static void generatePermutations(String str, String ans) {
if (str.length() == 0) {
System.out.println(ans);
return;
}

for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
String remaining = str.substring(0, i) + str.substring(i + 1);
generatePermutations(remaining, ans + ch);
}
}
}``````

Output:

``````abc
acb
bac
bca
cab
cba
All permutations of abc have been displayed.``````

Step by Step Explanation:

Setting Up the String:
``        String input = "abc";``
We initialized a string named input which we want to generate permutations for.
Base Case:
``````        if (str.length() == 0) {
System.out.println(ans);
return;
}``````
Our recursive function, generatePermutations, will work by picking characters from str and adding them to ans. The base case is when str becomes empty, meaning we have formed a permutation in ans, which we then print.
Recursive Permutations Generation:
``````        for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
String remaining = str.substring(0, i) + str.substring(i + 1);
generatePermutations(remaining, ans + ch);
}``````
This loop traverses through each character in the string. For every character:
• We pick it out (denoted by ch).
• Generate a new string remaining which is the original string minus the picked character.
• We call our function recursively with this new string, adding our chosen character to the ans string.
Recursive Magic:
This process will keep repeating until every character has been the starting character, and we've explored all possible combinations of the remaining characters.

Conclusion

Generating permutations of a string is a classic example of a problem that can be elegantly and efficiently solved using recursion. This beginner's guide provides a clear pathway to understanding and implementing this solution in Java. Remember, recursion can initially feel a little tricky, but with practice, its patterns and beauty will become evident.