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;
}

function getAllPermutationsOfASet(text) {
  var results = [];

  if (text.length === 1) {
    results.push(text);
    return results;
  }

  for (var i = 0; i < text.length; i++) {
    var first = text[i];
    var remains = text.substring(0, i) + text.substring(i + 1);
    var innerPermutations = getAllPermutationsOfASet(remains);
    for (var j = 0; j < innerPermutations.length; j++) {
      results.push(first + innerPermutations[j]);
    }
  }

  return results;
}

Textbooks#

More posts tagged Interview question#