String permutations algorithm

I’ve recently been solving some Leetcode problems so decided to share one of them.

The problem Given a string cats, print all its permutations. By permutation means rearrangement of the characters in a given string. The order of characters matters in a permutation.

Breakdown

Let’s break the problem into subproblems. How could we re-phrase the problem of getting all permutations for cats in terms of a smaller but similar subproblems?

Let’s assume that our subproblem is getting all permutations for all the characters except the last one. It means that we should have permutations for cat. Just for reference here are all 6 possible permutations:

cat # 1
cta # 2
atc # 3
act # 4
tac # 5
tca # 6

Now our task is simply to put the s character in each possible position for each of the above permutations.

Lets start from the first one - cat. If we place s in all possible positions here is what we’ll get:

cat
	<s>cat
	c<s>at
	ca<s>t
	cat<s>

Correspondingly for second one cta it will look like this:

cta
	<s>cta
	c<s>ta
	ct<s>a
	cta<s>

And so on.

Here is the illustration showing all the permutations of cats.

The problem is that we don’t have a permutation for cat. But we can get it following exactly the same logic. If we need all the permutations for cat, we take all permutations for ca and then put t in each possible position in each of the permutations of ca.

Here is the illustration showing all the permutations of cat.

And once again, we don’t have the permutations of ca, how do we get it? Following the established logic we need to split it. We extract the last character a and place it into all the possible positions of the reminder string c. As c consists of single character we cannot split it further. We reached our base case. This is an easy task we can do by placing a in first position and into the last one:

ca
	ca
	ac

Here is the illustration showing all the permutations of ca.

Looking at the image below you can see that this is a recursive process.

Solution

As shown above we can use recursive approach to solve the problem.

Lets define our function that will be calculating permutations. This function will be called recursively.

const getPermutations = (str) => {
  const permutations = new Set();

  // TODO: add the logic of calculating permutations

  return permutations;
};

We are using set to make sure that there are no duplicates. It simplifies the code a bit as we don’t need to check if string was present before.

Then we add a handling of the base case. As identified above our base case is a single character. After extracting last character from ca string we were left with c. c is our base case. Once we reached it, there is not much we can do so we simply return this character. To not break function’s signature we return a set with single character.

const getPermutations = (str) => {
  const permutations = new Set();

  // base case
  if (str.length <= 1) {
    permutations.add(str);
    return permutations;
  }

  // TODO: add the logic of calculating permutations

  return permutations;
};

If the string contains more than one character we need to split it. We do it by separating the last character.

const getPermutations = (str) => {
  const permutations = new Set();

  // base case
  if (str.length <= 1) {
    permutations.add(str);
    return permutations;
  }

  const lastChar = str[str.length - 1];
  // all the characters except last
  const substr = str.slice(0, -1);

  // TODO: add the logic of calculating permutations

  return permutations;
};

Now we need to put the last character into all the possible permutations of the remaining string. For now we don’t have it but lets assume that we do. Just to follow with the process we put a placeholder in a form of an empty set. To put the last character in all the possible positions of available permutations we need to iterate over all of them:

const getPermutations = (str) => {
  const permutations = new Set();

  // base case
  if (str.length <= 1) {
    permutations.add(str);
    return permutations;
  }

  const lastChar = str[str.length - 1];
  // all the characters except last
  const substr = str.slice(0, -1);

  // TODO: find all possible permutations
  // for all chars except last recursively
  const partialPermutations = new Set();

  // put the last char in all possible positions
  // for each of the above permutations
  partialPermutations.forEach((permStr) => {
    // TODO: generate permutations
  });

  return permutations;
};

Generating a permutation is rather easy. We simply put the character in all the positions.

const getPermutations = (str) => {
  const permutations = new Set();

  // base case
  if (str.length <= 1) {
    permutations.add(str);
    return permutations;
  }

  const lastChar = str[str.length - 1];
  // all the characters except last
  const substr = str.slice(0, -1);

  // TODO: find all possible permutations
  // for all chars except last recursively
  const partialPermutations = new Set();

  // put the last char in all possible positions
  // for each of the above permutations
  partialPermutations.forEach((permStr) => {
    for (let i = 0; i <= permStr.length; i++) {
      const permutation = permStr.slice(0, i) + lastChar + permStr.slice(i);

      permutations.add(permutation);
    }
  });

  return permutations;
};

And the very last thing we need to do is to find out all the permutations for our string except the last character which is defined as allCharsExceptLast. We can easily do it by calling our function recursively.

const getPermutations = (str) => {
  const permutations = new Set();

  // base case
  if (str.length <= 1) {
    permutations.add(str);
    return permutations;
  }

  const lastChar = str[str.length - 1];
  // all the characters except last
  const substr = str.slice(0, -1);

  // get all possible permutations
  // for all chars except last recursively
  const partialPermutations = getPermutations(substr);

  // put the last char in all possible positions
  // for each of the above permutations
  partialPermutations.forEach((permStr) => {
    for (let i = 0; i <= permStr.length; i++) {
      const permutation = permStr.slice(0, i) + lastChar + permStr.slice(i);

      permutations.add(permutation);
    }
  });

  return permutations;
};