What is a Permutation?

A permutation is a distinct combination of the same set of digits. For example, a permutation of “abc” is “bca”. A common computer problem is finding all possible permutations of a given string of characters. The string “abcd” would have 24 possible permutations to print out, for example.

Calculating Permutation Counts Directly

The number of permutations for a given set of characters is the factorial of the count. For example, “abcd” has 4 characters, so 4! = 4 * 3 * 2 * 1 = 24 permutations.

How Should We Generate Permutations?

You can generate permutations in a number of ways… but I think the easiest one is to use a functional paradigm. This is very similar to the approach we used in the Locker Number No Repeats problem here: https://coding-stream-of-consciousness.com/2018/09/19/locker-number-w-o-repeats/.

The approach is:
– Make a recursive helper method that takes in just the target string of characters.
– Have it call a private recursive method with 2 parameters; a string representing the currently selected characters (will be empty) and a string representing the remaining/unused characters (will be set to the input string) and return the count of the found permutations.
– Make the private recursive method taking the 2 parameters noted earlier.
– If no characters are left in the unused character list, we have a solution; print it. Also, return 1 to count that solution.
– Otherwise, cycle through the remaining characters; ror each, recursively call the function with (1) The current string + the current remaining character and (2) all remaining characters except the current one we are processing.
– Track and return the sum of solutions from all the recursive calls.

Java Implementation

public class FunctionalPermutation {

  //Recursive helper function - gets recursion started.
  public static int permute(String s) {
    if (s == null) return 0;
    return permute("", s);
  }

  private static int permute(String c, String r) {

    //If no letters remain in r, we have a solution.  Print
    //it and return 1 to count it.
    if (r.length() == 0) {
      System.out.println(c);
      return 1;
    }

    //Recurse once for each remaining letter
    //in r, adding each to the current string.
    //Pass all letters but the added one into
    //the recursive call as remaining letters.
    //Also, sum up the number of solutions.
    int sum = 0;
    for (int i = 0; i < r.length(); ++i) {
      sum += permute(c + r.charAt(i), 
        r.substring(0, i) + r.substring(i + 1));
    }
    return sum;
  }

  public static void main(String[] args) {
    System.out.println("Permutation Count: " + permute("abcd"));
  }
}

Output

dbca
dcab
dcba
Permutation Count: 24