Javascript recursive permutation generator

Question

I'm trying to implement a recursive permutation generator in Javascript, but I can't seem to get it to go through all the recursion branches (see the Results below).

I know I'm missing something important, can someone help me understand where I've gone wrong?

    var permute = function(input){
        var permutation = function (arr, position){
            if(position >= arr.length-1){
                results.push(arr);
            }else{
                var tempSwap="";
                for(i=position;i<arr.length;i++){
                    tempSwap = arr[position];
                    arr.splice(position,1,arr[i]);
                    arr.splice(i,1,tempSwap);
                    permutation(arr,(position+1));
            }
            return;
        }
    };

    permutation(input,0);
};

var results=[];
permute(['a','b','c']);
console.log(results);

Results: [ [ 'a', 'c', 'b' ], [ 'a', 'c', 'b' ] ]

Answer 1

There were two errors: you was working on the same array without making copies and your loop counter i was a global variable. Fixed code:

 var permute = function(input){
        var permutation = function (arr, position){
            if(position == arr.length-1){ // >= was redundant and confusing
                results.push(arr);
            }else{
                for(var i=position;i<arr.length;i++){ // use local i
                    var tempSwap = arr[position];
                    arr.splice(position,1,arr[i]);
                    arr.splice(i,1,tempSwap);
                    permutation(arr.slice(),(position+1)); // you need a copy here
            }
            return;
        }
    };

    permutation(input,0);
};

var results=[];
permute(['a','b','c']);
console.log(results.join(' ')); // a,b,c a,c,b b,a,c b,c,a c,a,b c,b,a

https://jsfiddle.net/sagqkchL/1/

Not making copies caused all of your result arrays to look the same. The global variable caused only 2 results being produced.

Answer 2

I know I'm missing important

Your i variable is implictly global. Declare it with var, and your basic problem will go away.

Also, as mentioned in the comments, you are not copying the input array so you're always modifying the same object (and end up with result[0] == result[1] == …); you end your recursion one level too early (the base case is when you've met the end, not before); and also you should create the results array within the permute function.

function permute(input){
    function permutation(arr, position){
        if(position >= arr.length) {
            results.push(arr);
        } else {
            permutation(arr, position+1); // nothing is swapped, no need to copy anything
                                          // you can also omit this line and start i=position
            for (var i=position+1; i<arr.length; i++) {
                var tmp = arr.slice();
                tmp[position] = arr[i];
                tmp[i] = arr[position];
                permutation(tmp, position+1);
            }
        }
    };
    var results = [];
    permutation(input, 0);
    return results;
};

console.log(permute(['a','b','c'])); // [["a","b","c"],["a","c","b"],["b","a","c"],["b","c","a"],["c","b","a"],["c","a","b"]]