Published by ∞ Level Up Coding
Featured by ★ Medium Curated

GitHub repo with completed solution code and test suite.

Given a string, return all permutations of the string.

When I sat down to solve this problem, I found it to be a great algorithm challenge. Why? While the task of manipulating a string may seem familiar on its surface, actually finding a complete solution requires us to handle some unexpected complexity, which provides the opportunity to utilize a recursive tree and build a bit of familiarity with the master theorem.

Note: There is more than one way to solve this problem. The solution model I explore here utilizes tools and concepts that I find broadly valuable for the solution of algorithmic challenges, and methods that I find intuitive for string manipulation within Javascript.

First things first: What is a permutation?

per·mu·ta·tion

Learn to pronounce

noun

a way, especially one of several possible variations, in which a set or number of things can be ordered or arranged.

So every string has a number of permutations into which its characters could be re-arranged. A string permutation is similar to an anagram. However, it does not need to be an existing word, but can simply be a re-arrangement of the characters.

An example of permutations of something other than a string would be this:

For just three colors, we can have six different permutations, or ordered combinations of those colors.

Another example of permutations would be a combination lock:

Uh-oh. The whole point of combination locks is that a relatively small amount of numbers can create a large enough number of ordered combinations to prohibit casual opening.

Suddenly, this whole string-manipulation problem seems a bit more intimidating.

So we’ve figured out what a permutation is, and established that (depending on the length of the string) we may be looking for a lot of them. Where to start?

When I see a challenge like this, my first instinct is two do two things:

1: Make an empty array. If my final solution may return more than one “correct” element (in this case, permutations), I’ll need a place to store them before I return the complete solution.

2: Iterate! If I need to find all the ordered combinations of characters in a string, creating a loop to iterate through all the characters in a string seems like a decent place to start.

let findPermutations = (string) => {

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    // do something
  }
  return permutationsArray
}

Before we jump straight into our iteration, let’s knock a few things out of the way.

What if the user enters an empty string, or an integer, or tries to run the function without entering anything at all? We can’t get all the permutations of a string if there’s no string.

let findPermutations = (string) => {

   if (!string || typeof string !== "string"){
    return "Please enter a string"
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    // do something
  }
  return permutationsArray
}

The new line of code will return an error message if the argument input into the function is falsey, or if it is not a string.

Okay, great!

But what if the string is really short? Like only-one-character short? That’s also a scenario where we don’t really need to mess with the whole iterating and pushing things into an array bit. If our string is, for example, just “a”, it only has one permutation — “a”. We can just return “a”.

let findPermutations = (string) => {

   if (!string || typeof string !== "string"){
    return "Please enter a string"
  } else if (string.length < 2 ){
    return string
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    // do something
  }
  return permutationsArray
}

Alright, now that’s out of the way, we can get back to our iterative loop.

The structure of our function in its current state now looks a bit similar to something called the master theorem.

The Master Theorem

What is the master theorem?

It is a set of steps for breaking down potentially complex challenges into a set of smaller problems. Many problems or technical challenges fall into the category of Divide and Conquer Algorithms, which require the would-be solver to break a piece of data down into smaller pieces until the pieces are simple enough to be solved directly.

Written out in pseudocode, it looks like this:

procedure p( input x of size n ):

if n < some constant k:

Solve x directly without recursion

else:

Create a subproblems of x, each having size n/b

Call procedure p recursively on each subproblem

Combine the results from the subproblems

A few important things happen here:

1: a conditional checks if the size of the input is smaller than a constant.

2: if the input is larger than said constant, the input is broken down into smaller pieces until they are all small enough to run the procedure on directly

3: when this is done, the results of all the pieces post-procedure can be combined and returned as a single large bit of data.

This approach to breaking down problems is often visualized as a tree (especially as this is often helpful for establishing down a problem’s time complexity. You can read more about time complexity and the master method here).

Want to read more about recursive trees and the master theorem? I like this synopsis from Cornell.

Note how similar this structure is to the following diagram of our specific challenge of finding all permutations of a string:

While our current function isn’t exactly the same as the abstracted pseudocode of our master theorem, we have established the logical path of returning one solution if our input is smaller than a constant (in our case, if string.length is less than 2), and if not, creating a list of subproblems to solve.

If you’ve flattened out nested arrays before, this approach may feel familiar. It’s can be a good starting point for a wide variety of challenges — it won’t be the relevant method for every problem, but provides a nice place to start.

Note: This approach does utilize recursion.

You can read more about recursion here, here (code examples in javascript), here (code examples in javascript), here (code examples in ruby), and here (code examples in python).

Okay, back to our code.

Now, if we want to utilize the master theorem approach, we can update our plan to something a bit more clear than // do something.

let findPermutations = (string) => {

   if (!string || typeof string !== "string"){
    return "Please enter a string"
  } else if (string.length < 2 ){
    return string
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    // Create a subproblems of string, each having size n/b
    // Call procedure p recursively on each subproblem
    // Combine the results from the subproblems
  }
  return permutationsArray
}

For ease, I’d like to assign the current element we’re iterating over to the variable char.

So the first thing we’re supposed to do is break our string down into sub-problems.

To start, we have our current character, aka string[i], aka char. To begin breaking down the rest of the string, we need to collect the remaining characters.

let findPermutations = (string) => {

   if (!string || typeof string !== "string"){
    return "Please enter a string"
  } else if (string.length < 2 ){
    return string
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    let char = string[i]
    let remainingChars = string.slice(0, i) + string.slice(i + 1, string.length)

    // Call procedure p recursively on each subproblem
    // Combine the results from the subproblems
  }
  return permutationsArray
}

Just as we assigned our current character to the variable char, let’s assign the remaining characters to the variable remainingChars.

Note: There are many different ways one might collect the remainingChars. This is just one method.

To collect those characters, we can use the string method slice. Substring is a similar method, so if you’re more familiar with that, you can use it instead. Slice is non-destructive, so we don’t need to worry about mutating our original string — the result we get by slicing our string will be its own new string.

So we’ll slice the characters from index 0 (the first character in the string) to index i (our current character, char). Then, we’ll join the characters from index i + 1 (the next character after char) to index string.length (the last character in string).

So now we have two smaller strings — char and remainingChars.

What now?

Well, let’s consult the master theorem:

Call procedure p recursively on each subproblem

So we’re going to call our findPermutations function on our remainingChars string.

Then what?

Combine the results from the subproblems

I knew we’d need that empty array.

Okay, so what does this look like in JavaScript?

let findPermutations = (string) => {
  if (!string || typeof string !== "string"){
    return "Please enter a string"
  } else if (string.length < 2 ){
    return string
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    let char = string[i]

    let remainingChars = string.slice(0, i) + string.slice(i + 1, string.length)

    for (let permutation of findPermutations(remainingChars)){
      permutationsArray.push(char + permutation) }
  }
  return permutationsArray
}

So we’ve done a few things here.

We recursively called findPermutations on remainingChars. For each result of that function, which I assigned to a variable named permutation, we can push a string that is the combination of char and permutation into our permutationsArray.

findPermutations("abc")

(6) ["abc", "acb", "bac", "bca", "cab", "cba"]

So let’s see what we get when we return permutationsArray.

Okay, great! When given the input “abc”, our findPermutations function returns all six permutations!

Let me try one more thing though.

findPermutations("aabc")

(24) ["aabc", "aacb", "abac", "abca", "acab", "acba", "aabc", "aacb", "abac", "abca", "acab", "acba", "baac", "baca", "baac", "baca", "bcaa", "bcaa", "caab", "caba", "caab", "caba", "cbaa", "cbaa"]

Well, that’s not good. If a character in our string repeats, we get each permutation twice. Lots of strings have repeating characters.

let findPermutations = (string) => {
  if (!string || typeof string !== "string"){
    return "Please enter a string"
  } else if (string.length < 2 ){
    return string
  }

  let permutationsArray = [] 

  for (let i = 0; i < string.length; i++){
    let char = string[i]

    if (string.indexOf(char) != i)
    continue

    let remainingChars = string.slice(0, i) + string.slice(i + 1, string.length)

    for (let permutation of findPermutations(remainingChars)){
      permutationsArray.push(char + permutation) }
  }
  return permutationsArray
}

There are a lot of different ways to remove superfluous elements, but I chose to use Javascript’s indexOf method to identify if the current character has already been run through our findPermutations method. indexOf returns the first index of a character, so if we’ve already run findPermutations for an “a”, for example, the indexOf(“a”) will be different than the index of char, the current, later “a”.

If this is true, we can continue, which will essentially skip the current iterative loop and move on to the next.

Let’s run findPermutation with this addition.

findPermutations("aabc")

(12) ["aabc", "aacb", "abac", "abca", "acab", "acba", "baac", "baca", "bcaa", "caab", "caba", "cbaa"]

Perfect! 🌟 A master theorem based approach allowed us to quickly break this problem down into bite sized pieces and begin returning correct results, leaving only a few tweaks needed here and there to deliver our solution in exactly the desired format.

Review:

So what was our master theorem based approach again?

1: Establish a base case — if our input’s size is less than a certain constant, solve it directly without recursion.

2: If the input is bigger than said constant, break it down into smaller pieces.

3: Call the function recursively on the pieces, until they are small enough to be solved directly.

4: Combine the results from the pieces, and return the completed solution.

I have found this model to be a really handy tool that reliably provides me with a place to start when tackling algorithmic challenges. While not specifically applicable to every algorithm problem, and not always the most performant or elegant solution, it’s a reliable workhorse model that can serve you well!

The GitHub repo containing the solution code also comes with a test suite, so you can practice or play around with finding alternate solutions for this problem if you like.

If you want to explore further, you could try using the solution model utilized above to find all the combinations of a combination lock? Does it work? Do you need to make any changes?