Implement All Permutations of a Set in JavaScript

Interview Questions
September 26, 2016

This is the second article in series about programming interview questions and how to think through and solve them! If you want to start from the beginning, check out even occurrence!

This article is covering a very common interview question, all permutations of a set. ‘Implement a function that gets all permutations or orderings of a given string. For example if the input is ‘abc’, the output should be [‘abc’, ‘acb’, ‘cab’, ‘cba’, ‘bca’, ‘bac’].

Analysis

A lot of people hear the word permutation and get scared, so let’s first tackle what a permutation actually is.

A permutation relates to the act of arranging all the members of a set into some sequence or order.

Easy! Well.. not quite, but at least we now know what we need to return at the end. That is, if we’re given ‘abc’; the result should be:

[ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Let’s first take a look at how this problem might naturally be solved. If given ‘abc’, I would naturally separate the first letter and find all permutations of the next two letters. So for “abc” I would have:

a bca cbb acb cac abc ba

In this case, my mind jumps straight to recursion because we don’t know how large the string will be in our test cases. So for all letters in the string, we can grab one letter of the string and prepend it to all of its permutations without the letter in it. In recursion we need our ‘base case’ when we want to stop our recursive call. In this case it will be when the string is a single character, we’ll 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 getAllPermutations (string) define results if string is a single character add the character to results return results for each char in string define innerPermutations as a char of string set innerPermutations to getAllPermutations (without next char) foreach string in innerPermutations add defined char and innerPermutations char return results

Complexity

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 the time and space complexity of our algorithm is O(n!).

Code

function getAllPermutations(string) { var results = []; if (string.length === 1) { results.push(string); return results; } for (var i = 0; i < string.length; i++) { var firstChar = string[i]; var charsLeft = string.substring(0, i) + string.substring(i + 1); var innerPermutations = getAllPermutations(charsLeft); for (var j = 0; j < innerPermutations.length; j++) { results.push(firstChar + innerPermutations[j]); } } return results; }

Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

More Blog Posts