Write a Program in Java to print all permutations of a string.
Example:
|
1 2 3 4 5 |
Input: lol Output: lol, llo, oll Input: hat Output: hat, aht, ath, hta, tha, tah |
The plan is to make use of recursion to solve this problem because every substring is itself a string.
Example:
|
1 2 |
l [ol, lo] o [ll] |
Also if the string contains duplicate alphabets then there is a sure chance that the same permutation value will be printed more than one time, Eg lol, lol. To check this we will store each already printed permutations into a list and whenever we form a new permutation we first check if that is already contained in the list or not and will only output it if it is not there in the list.
So let’s print all permutation of the string in Java.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import java.util.List; import java.util.ArrayList; import java.util.Scanner; class Main { static List<String> output = new ArrayList<>(); public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("Enter a string"); String str = in.next(); //call permustion with empty string as 1st and //input-string as second parameter System.out.println("All Permutations"); permutation("",str); } public static void permutation(String perm, String word){ if(word.isEmpty()){ //check if word is prsent in the list if(!output.contains(perm)){ //if no then print and store System.out.println(perm); output.add(perm); } } //1. Loop //2. Split //3. Recursive call for(int i=0; i<word.length(); i++){ permutation(perm+word.charAt(i), word.substring(0,i)+word.substring(i+1,word.length())); } } } |
Output
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Enter a string lol All Permutations lol llo oll Enter a string 123 All Permutations 123 132 213 231 312 321 |
We can also input number to print all its permutation in the above program because it will be treated as a string. All permutations of a string can also be said as anagrams of a string, so the above program is also the program for all anagrams of a string.