Print all possible strings of length K that can be formed from a set of N characters in Java

Find all n length Permutation of a given String.
OR
Print all combinations/permutations of a string 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

---

Print all possible strings of length K that can be formed from a set of N characters in Java. Lets see sample input and output below,

Case 1  
Input: string=AB and length=2
Output:

1. AA
2. AB
3. BA
4. BB

Case 2
Input: string=ABC and length=2
Output:

1. AA
2. AB
3. AC
4. BA
5. BB
6. BC
7. CA
8. CB
9. 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 in 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

Stack trace of printing all possible strings of length K that can be formed from a set of N characters

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

package javabypatel;

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);
  }
 }
 
}

Another approach

package javabypatel;

import java.util.Arrays;

public class GenerateAllPermutationOfNBits {

    public void printCombination(int[] arr, int i, int lengthOfCombination, int combinationSet) {
        if (i == lengthOfCombination) {
            System.out.println(Arrays.toString(arr));
            return;
        }

        for (int j=0; j<combinationSet; j++) {
            arr[i] = j;
            printCombination(arr, i+1, lengthOfCombination, combinationSet);
        }
    }

    public void printCombinationOfGivenSet(char[] arr, int i, int lengthOfCombination, char[] combinationSet) {
        if (i == lengthOfCombination) {
            System.out.println(Arrays.toString(arr));
            return;
        }

        for (int j=0; j<combinationSet.length; j++) {
            arr[i] = combinationSet[j];
            printCombinationOfGivenSet(arr, i+1, lengthOfCombination, combinationSet);
        }
    }

    public static void main(String[] args) {
        GenerateAllPermutationOfNBits obj = new GenerateAllPermutationOfNBits();
        int lengthOfCombination = 2; //(length of the combination to generate)
        int combinationSet = 2;
        //(2 means use 0 and 1 while generating combination)
        //(3 means use 0, 1 and 2 while generating combination)

        obj.printCombination(new int[lengthOfCombination], 0, lengthOfCombination, combinationSet);

        System.out.println("Print from Given set...");
        char[] combinationSetArr = new char[]{'A', 'B', 'C'};
        obj.printCombinationOfGivenSet(new char[lengthOfCombination], 0, lengthOfCombination, combinationSetArr);
    }
}

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.