Step-by-Step Guide to Solving String Permutation Using Recursion in JavaScript

Tackling permutations and recursion one step at a time.

Solving a permutation problem with recursion has been particularly difficult for me to wrap my head around. It just doesn’t seem as natural as iteration. So let’s take a gentle journey, you and me. We’ll walk through a recursive solution together. Step-by-step.

This is my dog Lula. Dog’s are comforting. So let’s think of cute fluffy pups while thinking of scary weird algorithms.

Lula last Easter

Lula’s a sweetie. A smartie pants. A loud barker. Let’s permute Lula. Or…her species. Or…the word “dog”. Let’s write a function that takes in a string (“DOG”) and outputs every combination possible of that word in an array.

But first, let’s note how we do this manually. How would we permute “DOG”? Here’s one approach:

• Let’s take the first letter of our string in put it in our memory: D
• Now, let’s take the remaining letters: O, G
• Let’s make one word by taking the remaining letters, and then add them to our first letter, one by one: D+ OG, and D+ GO. So we now have 2 permutations: DOG, and DGO.
• Let’s move on to the second letter: O, and take the remaining letter and set them aside: D and G.
• Let’s make another permutation of those: O + DG, and O + GD. Now we have 4 permutations: DOG, DGO, ODG, OGD.
• Now let’s tackle the last letter: G. And set aside the remaining letters: D and O.
• Let’s make permutation of that: G + DO, and G + OD. Now we have 6 permutations: DOG, DGO, ODG, OGD, GDO, GOD.
• We’d now just have to return all these combinations in an array.

Notice what we’re doing here:

• We’re taking the string (“DOG”), and iterating through it one letter at a time.
• We then take the remaining letters, and iterate through those remaining ones, one letter at a time.
• When we’re down to one letter, we add it to that first letter we took a look at.
• We keep doing this until we’ve done this with all letters.

This is recursion. Let’s code it up using JavaScript.

Let’s define a function (findPerms) that takes in a string (str). The first thing I like to do with recursive functions is think of the base case. This is when we know we can’t break down our problem into a smaller component. In this case, I’d argue we have two base cases:

1. When our string is empty (really, more like an edge case for bad or unexpected input).
2. When our string has only one letter. Because if we just get one letter (e.g. A), then we just return that. There’s nothing to permute.

So let’s start with that:

function findPerms(str) {
  if (str.length === 0) return "";
  if (str.length === 1) return str;
}

Next, let’s create an empty array to house our result for more common inputs, and make sure we return it at the end. Then, let’s chop our word up like we did above: let’s take one letter at a time in our string, and then deal with the remaining letters separately:

function findPerms(str) {
  if (str.length === 0) return "";
  if (str.length === 1) return str;
let result = [];
for (let i = 0; i < str.length; i++) {
    const currentChar = str[i];
    const remainingChars = str.slice(0, i) + str.slice(i + 1);
  }
  return result;
}

We want to look at each letter. So we’ve started a for loop. Inside that for loop, we’ve created two variables:

• currentChar: that current letter we’re iterating with
• remainingChars: all other characters in the string except the letter we’re iterating with.

Now comes the interesting part. We have to iterate through our remainingChars variable so that we can chop those characters as well, and deal with those individually.

function findPerms(str) {
  if (str.length === 0) return "";
  if (str.length === 1) return str;
let result = [];
for (let i = 0; i < str.length; i++) {
    const currentChar = str[i];
    const remainingChars = str.slice(0, i) + str.slice(i + 1);
for (let j = 0; j < remainingChars.length; j++) {

    }
  }
  return result;
}

What should we do with those remaining characters? The same thing we did before: we have to chop it down until we only have one character, and then, add it or concatenate it to the currentChar so we can build all our results. Consider, we’ve already written something that chops strings down. It’s the function we’re building! So let’s call upon it again, but only with the iteration of the remaining characters we last called:

(1) function findPerms(str) {
(2)  if (str.length === 0) return "";
(3)  if (str.length === 1) return str;
(4) let result = [];
(5) for (let i = 0; i < str.length; i++) {
(6)    const currentChar = str[i];
(7)    const remainingChars = str.slice(0, i) + str.slice(i + 1);
(8) for (let j = 0; j < remainingChars.length; j++) {
(9)      result.push(currentChar + findPerms(remainingChars)[j]);
(10)    }
(11)  }
(12)  return result;
(13)}

This the part that will continue calling upon itself until we hit a base case- in the case, until we have only one letter. It will then add it the currentChar, and push that into the result array. As each recursive function call resolves, the permutations will fill our array.

It’s kind of confusing, and hard to keep track of it call, so let’s walk through the code a bit, step-by-step

Me trying to keep track of all the recursion calls in my head

Code Walk-through

• We call our function with the string “DOG”.
• When i = 0, currentChar = D, and remainingChars = “OG”
• When j = 0, we’ll call our function again, but this time with the string “OG” (line 9).

Remember, because this is recursion, we’re starting all over again….

• When i = 0, currentChar = O, and remainingChars = “G”
• We then call our function again, this time just with the string “G” (line 9).
• Because we’re calling our string with only “G”, and that’s length 1, we now return the input str, which is “G” (line 3).
• So now a “G” is being returned to the previous function call, which said to push that result with the currentChar (“O”) into the results array. So now, our result array has [“OG”] in it.
• Now j = 1, meaning the second loop’s counter incremented to look at the next letter when we called it with “OG”. Thus, the currentChar is now “G”, and remainingChars is now “O”.
• We call our function again with the string “O”, which would return the “O” back, and add it to the currentChar “G”. It’s now then pushed into the results array. So we now have [“OG”, “GO”] in our results array.
• Now that these two function calls resolve, the original call has its results, so it’ll push both the “OG” and the “GO” with its currentChar “D” into its results array.
• Thus, the results array at this point now has [“DOG”, “DGO”].

As you might’ve guessed, the first loop will now increment, and look at letter “O” as its currentChar, and “DG” as its remainingChars. The same exact process we walked through will execute again until it iterates through those characters, and will push the return values into the results array.

After all iterations complete, the function returns the results array:

[“DOG”, “DGO”, “ODG”, “OGD”, “GDO”, “GOD”]

These are all the permutations of the string “DOG”.

Thanks for reading! And remember…

Grit > talent.

UPDATE

It’s been brought to my attention by both Jim White (jim.white@me.com) and commentator Hyunho NOH that there’s a bug in this code for strings longer than 3 characters. I’ve adjusted the code to fix this (below), but can you see why there’s a difference? Does it make sense? Share in the comments!

function findPerms(str) {
  if (str.length === 0) return "";
  if (str.length === 1) return str;
  let result = [];
  for (let i = 0; i < str.length; i++) {
    const currentChar = str[i];
    const remainingChars = str.slice(0, i) + str.slice(i + 1);
    const remainingCharsPermuted = findPerms(remainingChars);
    for (let j = 0; j < remainingCharsPermuted.length; j++){
      const permutation = currentChar + remainingCharsPermuted[j]
      result.push(permutation)
    }
  }
  return (result);
}