## The question

Generate all permutations of a given string.

## My solution

This is a question that I had been asked before and I wasn’t able to solve in the duration of an interview. I took some time to think about the problem and this is what I came with.

There are going to be n! permutations so that is what I should expect. The permutations of a string of length 1 is the string itself. The permutations for a string of length two is the string and the reversed string. With this in mind I came up with this recursive algorithm:

– The name of the function will be **permute**

– If the length of the input is 1 then return the string

– If the length of the input is 2 then return the string and the reversed string

– If the length of the string is more than 2 then initialize an empty array and start with the first character:

– Remove current character from string and get all the permutations for that string using **permute**

– Do the same removing one character at a time

– When you are done with the characters then return the permutations array

The code explains it better:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

function permute(input) {
var permutations = [];
if (input.length === 2) {
permutations.push(input);
permutations.push(input[1] + input[0] + '');
return permutations;
}
for (var i = 0; i < input.length; i++) {
var p = permute(input.substr(0, i) + input.substr(i + 1));
for (var j in p) {
permutations.push(input[i] + p[j]);
}
}
return permutations;
}
function test() {
var permutations = permute('abc');
var expected = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'];
if (JSON.stringify(expected) === JSON.stringify(permutations)) {
console.log('success');
}
}
test(); // Prints success

I am not sure about the complexity of this algorithm but I think it would be n! if it wasn’t because I am moving permutations from one array to another.

## The best solution

The solution proposed by Arden suggests the following: Given a string of length n, get the permutations of the sub-string with length n-1 and then insert the missing letter in all possible positions within the permutations.

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

function permute(input) {
if (input.length <= 1) {
return [input];
}
// Get all permutations for length - 1
var perms = permute(input.substring(1));
var c = input[0];
var res = [];
// Place c in all posible locations within the permutations
for (var p in perms) {
for (var i = 0; i < input.length; i++) {
res.push(perms[p].substring(0, i) + c + perms[p].substring(i));
}
}
return res;
}
function test() {
var permutations = permute('abc');
var expected = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba'];
if (JSON.stringify(expected) === JSON.stringify(permutations)) {
console.log('success');
}
}
test(); // Prints success

I ran both solutions a few times and Ardens solution performs better than mine. This is probably because I do more string and array operations than him.

application_design

computer_science

algorithms

javascript

programming

]