All permutations of a string

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.