How to Find All Permutations of a Given String in Java

The permutation is the mathematical technique to determine the number of possible arrangements in a set when the order of the arrangement matters.

Permutations of a String Using Recursion

The function permutationFinder(String str) is recursive that prints every permutation of the string passed. The Set variable is used to store the permutations of a Java string so that duplicates are removed automatically. We chop our words, taking one letter at a time in our string, and deal with the remaining letters separately.

The insertChar function inserts the first character to get the complete list of permutations for the string we passed.

We begin with the string “ABC”, we iterate through it, one letter at a time. We separate our initial character, A, and the remaining ones are BC. Now we iterate through the rem and find the permutations for the remaining letters. The process is further explained below.

The permutationFinder() function is fired until we have nothing to chop; that is why we get rem = "". At this point, we add "" to perms and return it, which is further stored into the Set variable, words. Also, remember our initial character at this moment is C.

We loop over each string in the Set words. We have strNew as the "" empty string, it goes down to the second for-loop in this case, we have i=0 which is equal to strNew.length(); thus, we call the insertChar("",C,0) method with the arguments at that point. This call returns C, which is added into perm.

We break out the loop and check if we have unfinished business. Thus, at this point, we have our initial value as B, and words have one element, which is C. Now, the loop repeats by adding B at different positons with C. Thus, we get BC and CB as two elements inside the Set words.

At this point, we are out of the loop and get the initial value as A. We further repeat this process and insert the initial character A at possible positions in our earlier permutations. Firstly, for BC, we get ABC BAC and BCA. Similarly, for the second permutation, CB, we do the same thing: insert the first letter at possible positions and get ACB, CAB, and CBA.

import java.util.HashSet;
import java.util.Set;

public class PermutationFinder {
  public static Set<String> permutationFinder(String str) {
    Set<String> perm = new HashSet<String>();
    if (str == null) {
      return null;
    } else if (str.length() == 0) {
      perm.add("");
      return perm;
    }
    char initial = str.charAt(0);
    String rem = str.substring(1);
    Set<String> words = permutationFinder(rem);
    for (String strNew : words) {
      for (int i = 0; i <= strNew.length(); i++) {
        perm.add(insertChar(strNew, initial, i));
      }
    }
    return perm;
  }

  public static String insertChar(String str, char c, int j) {
    String begin = str.substring(0, j);
    String end = str.substring(j);
    return begin + c + end;
  }
  public static void main(String args[]) {
    String s1 = "ABC";
    System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
  }
}

These are all the possible permutations of the string “ABC”.

Output:

Permutations for ABC are: 
[ACB, BCA, ABC, CBA, BAC, CAB]