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

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

   Case 1
      Input:   A
      output: A
     
  Case 2
      Input: AB
      output:
                AB
                BA
               
  Case 3
      Input:  ABC
      output:
                ABC
                ACB
                BAC
                BCA
                CAB
                CBA
 

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!.
  So for "AB", total permutations are 2! = 2.
  For "ABC", total permutations are 3! = 6.

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  "permutation" that need to be printed and removing the same character one by one 
  from original string. As we are removing one by one character from original string and adding it to "permutation" string,   So it is sure at one point length of original String will be 0 and length of 
"permutation" string will be 3.
 
  So base case is, when the length of our original string became 0, we will print the string  "permutation" and return.
 
  Now, how we will form "permutation" string is, 
       remove first character of original string and add it to "permutation" string and check the 
       length of original string which is not 0, true, so call function again,
       "string" = "BC" "permutation" = "A"
     
       remove first character of original string and add it to "permutation" string and check the 
       length of original string which is not 0, true, so call function again,
       "string" = "C" "permutation" = "AB"
     
      remove remaining character of original string and add it to "permutation" string and check the 
      length of original string which is not 0, false, so it is time to print the string "permutation".
      "string" = "" "permutation" = "ABC"
     
      1st permutation is ABC
      after returning from printing 1st permutation,
      "string" = "C" "permutation" = "AB" 
              Original string has only one character "C" whose permutation is covered, 
              no more permutation possible of one character string, so return,
      "string" = "BC" "permutation" = "A"
               From original string "ABC", we covered permutation keeping 
              "A", "B" at place and changing "C", which gave "ABC" as 1st permutation.
               Now, its time to work on 2nd character of original string

       Now,
       remove second character of original string and add it to "permutation" string and check the 
       length of original string which is not 0, true, so call function again,
       "string" = "B" "permutation" = "AC"
     
      remove remaining character of original string and add it to "permutation" string and check the 
      length of original string which is not 0, false, so it is time to print the string "permutation".
      "string" = "" "permutation" = "ACB"
     
      if we continue the same process in a loop, then we will get all our permutations 
      without repetition of characters.

Program to print all permutations of a string in Java

package backtracking;

public class StringPermutationWithoutRepetition {
 
 public static void main(String[] args) {
  permutation("ABC");
 }
 
 private static void permutation(String string) {
  printPermutation(string,"");
 }

 private static void printPermutation(String string, String permutation) {
  
  if(string.length()==0){
   System.out.println(permutation);
   return;
  }
  
  for (int i = 0; i < string.length(); i++) {
   char toAppendToPermutation = string.charAt(i);
   String remaining = string.substring(0, i) + string.substring(i + 1);
   
   printPermutation( remaining,  permutation + toAppendToPermutation);
  }  
 }

}

Time Complexity:


Time complexity of program to print all permutations of a string is O(n*n!).

How it comes to (n * n!)

From the above stack trace picture of a program you can see, for printing permutation of string "ABC" i.e. 3 character word, what it does is 

Outer:
Keeping A at place, it finds all the permutations of remaining string, then,
          Inner:
          Keeping B at place, it finds all the permutations of remaining string, then,
                     keeping C at place, it finds all the permutations of remaining string, then,
          Change B to C and find all the permutations of remaining string, then, 
                     ...........
           ...............             
Keeping B at place, it finds all the permutations of remaining string, then,
           ...........
           ...........
Keeping C at place, it finds all the permutations of remaining string.

How many times Outer: label has to print is number of characters present in word.
that is n
How many times Inner: label has to print is number of permutations of a character present in word.
this brings n!
 
Now, if we read this line again,
Keeping Outer character at place, find all permutation of Inner sting, then replace 
Outer character at place, and again find all permutation of Inner sting, and 
so on till end of Outer character.

hence the complexity is O(n * n! )

You may also like to see


Write a program to print all permutations of a given string with repetition. (Repetition of characters is 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.

2 comments

Thanks for great explanation and great coding. What is the time complexity of your approach?

Reply

Thanks Hengame. I have updated the post and covered Time complexity. Please let me know if you find any difficulty in understanding it.

Reply

Post a Comment