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

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

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