## Problem

Implement a function that gets all possible *permutations* (or orderings) of the characters in a string. For example for the input string `"abc"`

, the output will be `"abc"`

, `"acb"`

, `"bac"`

, `"bca"`

, `"cab"`

and `"cba"`

.

## Analysis

This problem is very similar to all combinations of a set, though the actual computing of the values will be quite different. Let's start by defining the inputs and outputs.

ArrayList<String> getPermutations(String characters);

Now let's look at how this problem is naturally solved. When I write down a set of permutations by hand, I tend to start with the first letter (`a`

), and then find all permutations without that letter in it. So for `"abc"`

I would write:

a bc a cb b ac b ca c ab c ba

This approach can be translated exactly into a recursive function in which for all letters in a string, we pull the letter out of the string and prepend it to all permutations of the string without that letter in it. The base case when the string is a single character will return the character.

permutations(abc) = a + permutations(bc) + b + permutations(ac) + c + permutations(ab) permutations(ab) = a + permutations(b) + b + permutations(a) permutations(a) = a

## Pseudocode

function getPermutations (string text) define results as string[] if text is a single character add the character to results return results foreach char c in text define innerPermutations as string[] set innerPermutations to getPermutations (text without c) foreach string s in innerPermutations add c + s to results return results

## Complexity

Much like all combinations of a set, the time and space complexity of the above algorithm should be the same as the number of items produced. The number of unique permutations of any set of size *n* is *n!*, therefore our algorithm is *O(n!)*.

## Code

public static ArrayList<String> getPermutations(String text) { ArrayList<String> results = new ArrayList<String>(); // the base case if (text.length() == 1) { results.add(text); return results; } for (int i = 0; i < text.length(); i++) { char first = text.charAt(i); String remains = text.substring(0, i) + text.substring(i + 1); ArrayList<String> innerPermutations = getPermutations(remains); for (int j = 0; j < innerPermutations.size(); j++) results.add(first + innerPermutations.get(j)); } return results; }