Permutations are like rearranging the letters in a word to create new words. It might not sound too exciting, but in the world of coding, it’s a superpower! Imagine having a bag of letters and figuring out all the different words you can make with them—that’s permutations.
This blog explores various approaches to generating permutations in Java, including recursion, iteration, and distinct permutations.
Using recursion
The Java program utilizes a recursive approach to generate permutations of a given string, implementing backtracking by swapping characters at different indices.
// Permutations of a String in Java
import java.io.*;
import java.util.*;
public class PermutationEx {
//swap function to swap two characters from indices idx and idx2
public static void swap(char[] arr, int idx, int idx2) {
char temp = arr[idx];
arr[idx] = arr[idx2];
arr[idx2] = temp;
}
public static void solve(char[] arr, int idx) {
if (idx == arr.length - 1) { //Base condition of recursion
System.out.print(String.valueOf(arr) + " ");
}
for (int i = idx; i < arr.length; i++) {
swap(arr, idx, i);
solve(arr, idx + 1);
swap(arr, idx, i);
}
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
System.out.print("Enter string to generate its permutations: ");
String str = scn.next(); //String input from the user
if (str.length() == 0 || str == null) {
return;
}
solve(str.toCharArray(), 0); //function call to find all the permutations
//toCharArray() converts a given string into a character array
}
}
Learn more about the Bubble Sort in Java and Binary Search in Java now!
Explanation of the code:
The provided Java code demonstrates the generation of permutations for a given string using recursion. The `PermutationEx` class defines a `solve` method that takes a character array (`arr`) and an index (`idx`). It recursively generates permutations by swapping characters at different indices, and once the base condition (`idx == arr.length – 1`) is met, it prints the current permutation.
The `swap` function facilitates the swapping of characters at specified indices. In the `main` method, the user is prompted to enter a string. The code ensures a valid non-empty string input, converts it to a character array using `toCharArray()`, and calls the `solve` method to initiate the recursive permutation generation. The permutations are then printed to the console.
This implementation showcases the elegance of recursive algorithms in generating permutations and provides a foundation for understanding more advanced string manipulation techniques in Java.
Output:
Enter string to generate its permutations: one
one oen noe neo eno e on Recursive Approach: Backtracking method
If we don’t want to convert a string into a character array, then we have another recursive implementation for generating all the permutations of string in Java.
// Permutations of a String in Java
import java.io.*;
import java.util.*;
public class PermutationEx{
public static void solve(String curr, String rem) {
if (rem.length() == 0) { //Base condition for recursion
System.out.print(curr + " ");
return;
}
for (int i = 0; i < rem.length(); i++) {
//Rest of the string excluding the current index character
String ros = rem.substring(0, i) + rem.substring(i + 1);
solve(curr + rem.charAt(i), ros);
}
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
System.out.print("Enter string to generate its permutations: ");
String str = scn.next();
solve("", str);
}
}
Explanation of the code:
The `PermutationEx` class defines a `solve` method that takes two parameters: `curr` (the current permutation being formed) and `rem` (the remaining characters to be considered). The base condition checks if `rem` is empty, and if so, it prints the current permutation and returns.
Within the `solve` method, a for loop iterates through each character of the remaining string (`rem`). For each character, it recursively calls `solve` with the updated `curr` and `rem` (excluding the current character).
In the `main` method, the user is prompted to enter a string. The code ensures a valid non-empty string input and then calls the `solve` method with an empty initial permutation (`””`) and the user-provided string (`str`).
This implementation showcases an alternative recursive approach for generating permutations, emphasizing the simplicity of string manipulation in Java.
Output:
Enter string to generate its permutations: none
none noen nnoe nneo neon neno onne onen onne onen oenn oenn nnoe nneo none noen neno neon enon enno eonn eonn enno enonIterative Approach
// Permutations of a String in Java
import java.io.*;
import java.util.*;
public class PermutationEx {
public static void permutations(String str) {
List<String> ans = new ArrayList<>(); //ArrayList
ans.add(String.valueOf(str.charAt(0)));
for (int i = 1; i < str.length(); i++) {
for (int j = ans.size() - 1; j >= 0; j--) {
String temp = ans.remove(j);
for (int k = 0; k <= temp.length(); k++) {
ans.add(temp.substring(0, k) + str.charAt(i) + temp.substring(k));
}
}
}
System.out.println(ans);
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
System.out.print("Enter a string : ");
String str = scn.next();
if (str.length() == 0 || str == null) {
return;
}
permutations(str);
}
}
Explanation of the code:
Java code generates permutations for a given string using an iterative approach. The `PermutationEx` class defines a `permutations` method that takes a string (`str`) as input. It uses an `ArrayList` (`ans`) to store the permutations.
The process starts by adding the first character of the string to the `ans` list. Then, for each subsequent character in the string, a nested loop iterates through the existing permutations in reverse order. For each permutation, it inserts the current character at every possible position and adds the modified permutations back to the list.
Finally, the generated permutations are printed to the console.
In the `main` method, the user is prompted to enter a string, and the code ensures a valid non-empty string input. The `permutations` method is then called with the user-provided string, demonstrating an efficient iterative approach to generate permutations in Java.
Output:
Enter a string : none
[eonn, oenn, onen, onne, eonn, oenn, onen, onne, enon, neon, noen, none, enon, neon, noen, none, enno, neno, nneo, nnoe, enno, neno, nneo, nnoe]Explore the fascinating world of OOPs in Java Check out!
Distinct Permutations of String in Java
Recursive Approach (Using Boolean Array)
// Permutations of a String in Java
import java.io.*;
import java.util.*;
public class PermutationEx {
public static void solve(String cur, String rem) {
if (rem.length() == 0) {
System.out.print(cur + " ");
return;
}
boolean visited[] = new boolean[60]; //Boolean Array
for (int i = 0; i < rem.length(); i++) {
char ch = rem.charAt(i);
String ros = rem.substring(0, i) + rem.substring(i + 1);
if (visited[ch - 'A'] == false) solve(cur + ch, ros);
//checking if the character has been already used
visited[ch - 'A'] = true;
//character has been marked as visited
}
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
System.out.print("Enter string to generate its permutations: ");
String str = scn.next();
solve("", str);
}
}
Explanation of the code:
This code generates permutations for a given string using recursion with a boolean array to keep track of visited characters.
1. The `PermutationEx` class has a `solve` method that takes two parameters: `cur` (the current permutation being formed) and `rem` (the remaining characters to be considered).
2. The base condition checks if `rem` is empty. If true, it prints the current permutation (`cur`) and returns.
3. The method uses a boolean array `visited` to keep track of visited characters. The array size is set to accommodate uppercase letters (A-Z).
4. The for loop iterates through each character of the remaining string (`rem`). For each character, it checks if it has been visited before. If not, it recursively calls `solve` with the updated `cur` and `rem`.
5. The character is then marked as visited in the `visited` array.
6. In the `main` method, the user is prompted to enter a string. The code ensures a valid non-empty string input, and then it calls the `solve` method with an empty initial permutation (`””`) and the user-provided string (`str`).
This implementation showcases how a boolean array can efficiently track visited characters during the recursive generation of permutations in Java.
Output:
Enter string to generate its permutations: new
new nwe enw ewn wne wen Recursive Approach (Using HashSet)
// Permutations of a String in Java
import java.io.*;
import java.util.*;
public class PermutationEx{
public static Set<String> solve(String str) {
Set<String> ans = new HashSet<String>(); //HashSet
if (str == null) {
return null;
}
else if (str.length() == 0){
//Base condition
ans.add("");
return ans;
}
char ch = str.charAt(0);
String rem = str.substring(1);
Set<String> temp = solve(rem);
//Recursive call that will return all the partial arrangements
for (String word : temp) {
//accessing each element of the set
for (int i = 0; i <= word.length(); i++) {
ans.add(word.substring(0, i) + ch + word.substring(i));
//inserting permutations in the set - ans
}
}
return ans;
}
public static void main(String[] args){
Scanner scn = new Scanner(System.in);
System.out.print("Enter string to generate its permutations: ");
String str = scn.next();
System.out.print(solve(str));
}
}
Explanation of the code:
This code generates permutations for a given string using recursion and a `HashSet` to store unique permutations. Let’s break down the code:
1. The `PermutationEx` class has a `solve` method that takes a string (`str`) as input and returns then a `HashSet` containing all the permutations.
2. The base conditions check if the string is `null` or empty. If true, it returns a set containing an empty string.
3. The method extracts the first character (`ch`) and then the remaining substring (`rem`) from the input string.
4. It makes a recursive call to `solve` with the remaining substring, obtaining a set of partial arrangements (`temp`).
5. The nested loops iterate through each partial arrangement and insert the current character (`ch`) at every possible position, generating permutations. These permutations are added to the `ans` set.
6. The final set of permutations is returned.
7. In the `main` method, the user is prompted to enter a string. The code ensures a valid non-empty string input and then calls the `solve` method, printing the resulting set of permutations.
This implementation showcases the use of a `HashSet` to efficiently store unique permutations during the recursive generation process in Java.
Output:
Enter string to generate its permutations: none
[onne, nnoe, neon, eonn, enno, oenn, enon, noen, nneo, none, neno, onen]Efficiency Considerations
A. Choosing the Right Permutation Method
When generating permutations of a string in Java, it’s like finding all possible arrangements of its characters. However, some methods are more efficient than others.
B. What Makes a Method Efficient?
Imagine you’re organizing a bookshelf. Different methods are like various strategies to arrange the books. Some consider every possibility, while others skip repeated efforts. The efficiency depends on factors like speed, memory usage, and how well it handles duplicates.
C. Optimal Use Cases
Think of these methods as tools in a toolbox. If you’re organizing a small bookshelf, any method might work. But for a giant library, you’d want the quickest and most memory-friendly tool. Each approach has its strengths—pick the one that suits your specific bookshelf (or string) size and organization needs!
In simple terms, it’s about finding the best way to tidy up your words, making sure your Java program organizes them swiftly and smartly!
Real-world Applications
A. Everyday Uses of String Permutations
Ever wonder how string permutations in Java apply to real life? It’s like figuring out all the possible ways to arrange your favorite toppings on a pizza! But in the programming world, it’s about solving problems.
B. Solving Puzzles and Challenges
Just like solving a tricky puzzle, Java programs use string permutations to tackle challenges. Think of it as finding the best moves in a game or the fastest route on a map. Programmers use these arrangements to crack codes, design efficient routes, and navigate complex situations.
In simpler terms, it’s like having a superpower to unravel hidden patterns and solve puzzles, moreover making Java programs smarter and more effective in the real world!
In conclusion, mastering string permutations in Java unlocks diverse approaches—recursion, iteration, and more. Whether converting to arrays or leveraging Boolean arrays and HashSets, efficiency considerations guide optimal choices. Beyond coding, real-world applications span puzzle-solving, game strategies, and complex problem-solving, making permutations a vital skill in Java programming.
We hope our blog on ‘Permutations of Strings in Java’ helps you to understand string programs in Java in a better way. Make sure to visit our Newtum website for additional information on a variety of subjects, including PHP, C Programming for kids, Java, and Happy coding!
About The Author
