Print all combinations/permutations of a string of length k that can be formed from a set of n characters

Find all n length Permutation of a given String.
OR
Print all possible strings of length k that can be formed from a set of n characters. OR.
Print all possible combinations of k elements from a given string of size n

Case 1  
  Input: string=AB and length=2
  Output:
    AA
    AB
    BA
    BB
   
Case 2
   Input: string=ABC and length=2
   Output:
    AA
    AB
    AC
    BA
    BB
    BC
    CA
    CB
    CC  

Algorithm:


  
How many permutations is possible?

How many permutations is possible can be calculated using k^r where,
  k = length of unique characters to use.
  r = number of places to fill. In first example above, k=2(A,B), r=2(all permutations of length 2 is required)
  2^2 = 4 permutations possible.

 In second example above, k=3(A,B,C), r=2(
all permutations of length 2 is required)
 3^2 = 9 permutations possible.
 

How to print all permutation?

It is very easy, Lets take an example of String "ABC" and we are told to generate permutations of length 3.    

using formula k^r we can see, 3^3 = 27 permutations possible.
We will take recursive approach i
n this approach important thing is base case.

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.
We will add the characters to the string "permutation" until the length of it is 3 as we want to find permutations of length 3.
  
So base case is, when the length of our string "permutation" matches given length, 

we will print the string "permutation" and return.
 

Working:
  
Now, how we will form "permutation" string is,
we have string "ABC" and we want to find all permutation of it consisting of length 3.
  
How we can do is,

First lets see how many permutation possible of length 1 of given string "ABC".
Answer is 3.
     A
     B
     C

So we can see that if we fill our third position by keeping first 2 place common, filled by "A", 

and only changing last place to possible permutation of length 1, we will get 3 permutations.
    
     A A A
     A A B
     A A C
  
and now if we repeat the same, but this time we will change the second position and then again iterate over possible permutation of length 1, we will again get 3 permutations.
    
     A B A
     A B B
     A B C
  
and now if we repeat the same, but this time we will change the second position and then again iterate over possible permutation of length 1, we will again get 3 permutations.
  
     A C A
     A C B
     A C C
  
and now if we repeat the same, but this time we can't change the second position as we have covered second place for all possible characters "A", "B" and "C" keeping "A" at first place fixed.
 

So, Now it is the time to change the first place position which is till now covered only for "A".
So this time we will change the first place position to "B" and again we will repeat above steps.
  
    B A A
    B A B
    B A C
  
    then,
  
    B B A
    B B B
    B B C
  
    then,
  
    B C A
    B C B
    B C C
  
So, now it is the time to change the first place position which is till now covered only for 

"A" and "B".
We will change the first place position to "C" and again we will repeat above steps.

    C A A
    C A B
    C A C
  
    then,
  
    C B A
    C B B
    C B C
  
    then,
  
    C C A
    C C B
    C C C
  
    done.
  

Program to print all combinations of string of length k in Java

package backtracking;

public class GenerateAllPermutationOfNBits {

 public static void main(String[] args) {
  permutation("ABC", "", 2);
  permutationOfBinaryNumbers("", 2);
 }
 
 private static void permutation(String str, String prefix, int lengthOfPermutationString){
  if(prefix.length()==lengthOfPermutationString){
   System.out.println(prefix);
  }else{
   for (int i = 0; i < str.length(); i++) {
    permutation(str, prefix + str.charAt(i), lengthOfPermutationString);
   }
  }
 }
 
 private static void permutationOfBinaryNumbers(String prefix, int lengthOfPermutationString){
  if(prefix.length()==lengthOfPermutationString){
   System.out.println(prefix);
  }else{
   permutationOfBinaryNumbers(prefix + "1", lengthOfPermutationString);
   permutationOfBinaryNumbers(prefix + "0", lengthOfPermutationString);
  }
 }
 
}


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).

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

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