Given a string of length n, print all permutation of the given string. Repetition of characters is allowed
Case 1Input: A
output: A
Case 2
Input: AB
output:
AA
AB
BA
BB
Case 3
Input: ABC
output:
AAA
AAB
AAC
ABA
ABB
ABC
ACA
ACB
ACC
BAA
BAB
BAC
BBA
BBB
BBC
BCA
BCB
BCC
CAA
CAB
CAC
CBA
CBB
CBC
CCA
CCB
CCC
Algorithm:
How many permutations is possible?
Lets see how many permutation is possible for given n character String.
In string "AB", n is 2
In string "ABC", n is 3
From above permutations displayed, we can see relation as n^n.So for "AB", total permutations are 2^2 = 4.
For "ABC", total permutations are 3^3 = 27.
How to print all permutation?
It is very easy, Lets take an example of String "ABC"
We will take recursive approach. In this approach important thing is base case.
We will try to make each permutation by adding characters one by one to the temporary String
that need to be printed.
As our string is of length 3, so we will add the characters to the temporary string that needs
to be printed till the length is 3 as permutation string length will be 3.
So base case is, when the length of our temporary string that needs to be printed is 3,
print and return.
Now, how we will form temporary string is,
add first character of string to temporary string and check the length of
temporary string which is less then 3, true, so call function again,
tempString = "A"
add first character of string to temporary string and check the length of
temporary string which is less then 3, true, so call function again,
tempString = "AA"
add first character of string to temporary string and check the length of
temporary string which is less then 3, false, so print and return
tempString = "AAA"
1st permutation is AAA
after returning from printing 1st permutation, tempString will be again "AA"
Now appending "B" to "AA" will make our 2nd permutation that is "AAB", print and return.
Now appending "C" to "AA" will make our 3rd permutation that is "AAC", print and return.
from this we can see, that keeping "AA" common and adding "A", "B", "C" that is
each character of String, we are getting permutation.
if we continue the same for 2nd position and then for 1st position of temporary string then
we will get all our permutations.
Java Program to print permutation of string with repetition
package javabypatel; public class StringPermutationWithRepetition { public static void main(String[] args) { printPermutationOfStrings("ABC"); } private static void printPermutationOfStrings(String str){ printPermutation(str, ""); } private static void printPermutation(String str, String stringToPrint){ if(stringToPrint.length()==str.length()){ System.out.println(stringToPrint); return; } for (int i = 0; i < str.length(); i++) { printPermutation(str, stringToPrint + str.charAt(i)); } } }Due to Immutable nature of String class, every time we create a different String literal a new object of String is created, In above approach, we append character to String variable "stringToPrint" and new String object is created. So to avoid creating new String in each append here, we should use array or some mutable datatype like StringBuffer here. Let's see the better approach below,
Optimized Approach:
package javabypatel; import java.util.Arrays; public class StringPermutationWithRepetition { public void printCombination(int n, String str, char[] arr) { if (n == arr.length) { System.out.println(Arrays.toString(arr)); return; } for (int i=0; i < str.length(); i++) { arr[n] = str.charAt(i); printCombination(n+1, str, arr); } } public static void main(String[] args) { StringPermutationWithRepetition obj = new StringPermutationWithRepetition(); String str = "AB"; obj.printCombination(0, str, new char[str.length()]); } }
You may also like to see
Write a program to print all permutations of a given string without repetition. (Repetition of characters is not allowed).
Print all combinations/permutations of a string of length k that can be formed from a set of n characters.
Print all subsets of a given set.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
Post a Comment