# 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: 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