I am looking for a review of my recursive function that generates the permutations of a string. Are there better ways to do this?

var permutations = [];

function doPerm(str, arr) {
    if (typeof (str) == 'string') str = str.split('');
    if (str.length == 0) permutations.push(arr.join(''));
    for (var i = 0; i < str.length; i++) {
        var x = str.splice(i, 1);
        doPerm(str, arr);
        str.splice(i, 0, x);
doPerm('', []);
  • 1
    \$\begingroup\$ good code , no improvement needed as per this context \$\endgroup\$
    – Paritosh
    Aug 10, 2014 at 9:57
  • \$\begingroup\$ An implementation of Heap's algorithm in JavaScript (mentioned in @amon's answer) can be found here. \$\endgroup\$
    – mjolka
    Aug 10, 2014 at 13:00
  • \$\begingroup\$ FYI, typeof is an operator, not a function. The parentheses around str are unnecessary and misleading. \$\endgroup\$
    – Ingo Bürk
    Aug 10, 2014 at 13:55

2 Answers 2


Your code seems to be correct, and is written in a good style. However, both the interface of your code as well as the algorithm used can be improved.

You currently have a global variable permutations which also contains the output. This variable will have to be cleared every time before doPerm is invoked. Instead, wrap doPerm in another function that provides initialization and input validation:

function perms(data) {
    if (!(data instanceof Array)) {
        throw new TypeError("input data must be an Array");

    data = data.slice();  // make a copy
    var permutations = [],
        stack = [];

    function doPerm() {
        if (data.length == 0) {
        for (var i = 0; i < data.length; i++) {
            var x = data.splice(i, 1);
            data.splice(i, 0, x);

    return permutations;

var input = "abcd".split('');
var result = perms(input);
for (var i = 0; i < result.length; i++) {
    result[i] = result[i].join('');

Note that this function will operate on arrays of any type and does not special-case strings.

Your algorithm currently relies on splicing elements into and out of the input array. This is somewhat expensive on larger data sets, and it would be better to generate the permutations by swapping. Heap's Algorithm does just this.

  • 1
    \$\begingroup\$ Nice, although I'd recommend throwing a TypeError instead \$\endgroup\$
    – Flambino
    Aug 10, 2014 at 11:06
  • 4
    \$\begingroup\$ I think perms and doPerm are horrible names. Why not choose something meaningful? \$\endgroup\$
    – Ingo Bürk
    Aug 10, 2014 at 13:55
  • 2
    \$\begingroup\$ @IngoBürk quite right, doPerm could be improved – I'd probably use _perms or recurse in my own code. However, I do not see anything wrong with the name perms for a function that calculates permutations. There's a balance to be found between explicitness and terseness, and I think perms is a name that strikes a good balance when used for a local variable or method name. \$\endgroup\$
    – amon
    Aug 10, 2014 at 14:29
  • 1
    \$\begingroup\$ @amon Personally, I tend to be descriptive, so I'd probably write something like calculatePermutations. But even if one doesn't want to do that, I think abbreviating is unnecessary here. permutations would be simple and short, but expressive. I like recurse for the inner function's name. \$\endgroup\$
    – Ingo Bürk
    Aug 10, 2014 at 15:06
  • \$\begingroup\$ great review, but why not replacing if (!(data instanceof Array)) { with if (!Array.isArray(data)) {? \$\endgroup\$ Aug 10, 2014 at 19:14

I modified your code after getting the error message: "too much recursion" for string of about 6 characters or so."

function getPermutations(str){
    //Enclosed data to be used by the internal recursive function permutate():
    var permutations = [],  //generated permutations stored here
        nextWord = [],      //next word builds up in here     
        chars = []          //collection for each recursion level
    //split words or numbers into an array of characters
    if (typeof str === 'string') chars = str.split(''); 
    else if (typeof str === 'number') {
      str = str + ""; //convert number to string
      chars = str.split('');//convert string into char array
    //============TWO Declaratives========
    return permutations;
    //===========UNDER THE HOOD===========
    function permutate(chars){ //recursive: generates the permutations
        if(chars.length === 0)permutations.push(nextWord.join(''));            
        for (var i=0; i < chars.length; i++){
            chars.push(chars.shift());  //rotate the characters
            nextWord.push(chars[0]);    //use the first char in the array            
            permutate(chars.slice(1));  //Recurse: array-less-one-char
            nextWord.pop();             //clear for nextWord (multiple pops)
}//==============END of getPermutations(str)=============

Some of the names are long, but descriptive.


  1. No longer get the "too much recursion" message.
  2. Only one argument is passed to the function.
  3. Takes a string or a number argument.
  4. Variables are not global but enclosed in the outer function.
  5. The inner function does the recursion using closure variables
  6. Doesn't use splice, but uses slice only once.

Anything else you can add of value or take away would be appreciated.

  • \$\begingroup\$ Created an account just to upvote this. By far my favorite expression / explanation of the algorithm. Thank you! \$\endgroup\$
    – bean
    Feb 19, 2016 at 2:00
  • \$\begingroup\$ A beautiful code. \$\endgroup\$
    – Kayote
    Jul 31, 2016 at 12:53
  • \$\begingroup\$ Wow. Beautiful remake of my post, thanks for sharing this! \$\endgroup\$
    – user44869
    Aug 31, 2016 at 17:11