Implement All Permutations of a Set in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach…

Implement All Permutations of a Set in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!

JavaScript eBook

I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. Check out the ebook now!

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’].

The Problem

Implementing all permutations of a set in JavaScript involves generating all possible arrangements of elements in a given set. To solve this problem, you need to design an algorithm that can efficiently generate permutations of the set. The algorithm should handle sets of various sizes and avoid duplicate permutations. JavaScript provides several approaches to implement this algorithm, such as using recursion or iteration with backtracking. By breaking down the problem, you can identify key steps, such as selecting elements, generating permutations recursively, and tracking visited elements to avoid duplicates. The solution to this problem allows JavaScript developers to generate and work with all possible permutations of a set, which can be useful for solving combinatorial problems, creating permutations-based algorithms, or generating test cases for algorithms involving permutations.

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 bc a cb b ac b ca c ab c baIn 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) +

c + permutations(ab)
``` ``` permutations(ab) = a + permutations(b) +
 b + permutations(a)
 

Pseudocode

 define results
 if string is a single character
 add the character to results

```javascript
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

#### JavaScript eBook

I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. [Check out the ebook now](https://www.mitrakos.com/ebook)!

I founded [Higglo Digital](https://higglo.io) and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a *beautifully designed website*, [check us out](https://higglo.io).

I also created [Wanderlust Extension](http://www.wanderlustapp.io/) to discover the most beautiful places across the world with highly curated content. Check it out!