Problems that involve permutations commonly involve recursivity as well. Basically, recursivity is defined as a process where some initial state is given and each successive state is defined in terms of the preceding state.

In our case, the state can be materialized by the letters of the given string. The initial state contains the initial string and each successive state can be computed by the following formula—each letter of the string will become the first letter of the string (swap positions) and then permute all of the remaining letters using a recursive call. While non-recursive or other recursive solutions exist, this is a classical solution to this problem.

Representing this solution for a string, ABC, can be done like so (notice how permutations are done):

Coding this algorithm will result in something like the following:

public static void permuteAndPrint(String str) {

  permuteAndPrint("", str);
}

private static void permuteAndPrint(String prefix, String str) {

  int n = str.length();

  if (n == 0) {
    System.out.print(prefix + " ");
  } else {
    for (int i = 0; i < n; i++) {
      permuteAndPrint(prefix + str.charAt(i),
        str.substring(i + 1, n) + str.substring(0, i));
    }
  }
}

Initially, the prefix should be an empty string, "". At each iteration, the prefix will concatenate (fix) the next letter from the string. The remaining letters are passed through the method again.

Let's suppose that this method lives in a utility class named Strings. You can call it like so:

Strings.permuteAndStore("ABC");

This will produce the following output:

ABC ACB BCA BAC CAB CBA

Notice that this solution prints the result on the screen. Storing the result implies adding Set to the implementation. It is preferable to use Set since it eliminates duplicates:

public static Set<String> permuteAndStore(String str) {

  return permuteAndStore("", str);
}

private static Set<String> 
    permuteAndStore(String prefix, String str) {

  Set<String> permutations = new HashSet<>();
  int n = str.length();

  if (n == 0) {
    permutations.add(prefix);
  } else {
    for (int i = 0; i < n; i++) {
      permutations.addAll(permuteAndStore(prefix + str.charAt(i),
        str.substring(i + 1, n) + str.substring(0, i)));
    }
  }

  return permutations;
}

For example, if the passed string is TEST, then Set will cause the following output (these are all unique permutations):

ETST SETT TEST TTSE STTE STET TETS TSTE TSET TTES ESTT ETTS

Using List instead of Set will result in the following output (notice the duplicates):

TEST TETS TSTE TSET TTES TTSE ESTT ESTT ETTS ETST ETST ETTS STTE STET STET STTE SETT SETT TTES TTSE TEST TETS TSTE TSET

There are 24 permutations. It is easy to determine the number of resulted permutations by computing the n factorial (n!). For n=4 (length of the string), 4! = 1 x 2 x 3 x 4 = 24. When expressed in recursive style, this is n! = n x (n-1)!.

Trying to implement this solution in Java 8 functional style will result in something like the following:

private static void permuteAndPrintStream(String prefix, String str) {

  int n = str.length();

  if (n == 0) {
    System.out.print(prefix + " ");
  } else {
    IntStream.range(0, n)
      .parallel()
      .forEach(i -> permuteAndPrintStream(prefix + str.charAt(i),
        str.substring(i + 1, n) + str.substring(0, i)));
  }
}

As a bonus, a solution that returns Stream<String> is available in the code bundled with this book.