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' ] ]

You're always acting on the same input array. You will need to create some copies! — Bergi
– Bergi, Commented Aug 11, 2015 at 19:03
its only going through 2 of 3 elements because of your arr.length-1. Your arrays length is 3. 3 minus 1 is 2. — Ole Haugset
– Ole Haugset, Commented Aug 11, 2015 at 19:03
You should use simple assignments instead of those splice calls. They're equivalent to arr[position] = arr[i]; arr[i] = tempSwap; — Bergi
– Bergi, Commented Aug 11, 2015 at 19:07
Thanks Bergi, I used this cleaner assignment in my final code too... — jazzhands
– jazzhands, Commented Aug 12, 2015 at 2:12

Maksim Solovjov · Accepted Answer · 2015-08-11 19:34:43Z

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.

edited Aug 11, 2015 at 19:34

answered Aug 11, 2015 at 19:27

Maksim Solovjov

3,16720 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

jazzhands Over a year ago

Thanks! I've been banging my head against this one forever, it was variable scoping!

Bergi · Accepted Answer · 2015-08-11 19:28:12Z

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"]]

Collectives™ on Stack Overflow

Javascript recursive permutation generator

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related