Write a program to print all permutations of a given string with repetition. (Repetition of characters is allowed).

Given a string of length n, print all permutation of the given string. Repetition of characters is allowed

---

   Case 1
      Input:   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.