Functional Permutations


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:

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) {
      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"));


Permutation Count: 24

2 thoughts on “Functional Permutations

  1. Pingback: Permutation – Live Coding Example – Java Interview | Quantum Code

  2. Pingback: Permutation – Live Coding Example – Java Interview | Coding and More

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s