Javascript recursion not functioning as expected

Question

I ported this method from Java to Javascript. With an "original" array with 9 objects in it, the Java code made 3000 subarrays of size 4.

In this javascript code I get 6 subarrays of size 9.

var hitterArray = new Array();

function permute(level, permuted, used, original){

    if (level == 4) {
        hitterArray.push(permuted); //array of arrays
    } else {
        for (i = 0; i < original.length; i++) {
            if (!used[i]) {
                used[i] = true;

                permuted.push(original[i]);

                permute(level + 1, permuted, used, original);

                used[i] = false;
            }
        }
    }
}

I want 3000 subarrays of size 4, why is that not working?

This is how I initialize the permute function:

            var used = new Array(results.length);
            for(p = 0; p < used.length; p++){
                used[p] = false;
            }
            var permuteArray = new Array();

            permute(0, permuteArray, used, results);

Insight appreciated

You might run into a callstack limitation which massive recursion often encounters. What error do you get? — TaoPR
– TaoPR, Commented Jul 14, 2015 at 8:52

Joao Leal · Accepted Answer · 2015-07-14 13:06:47Z

1

I think the error is on your for loop, you need to declare the i with var otherwise you make it a global variable.

for(var i = 0; ....

Another thing which might have impact is that you are always passing references to the arrays: used and permuted that is likely to have some impact on the result, consider cloning the arrays with array.slice() to create new copies of them.

And also I think the permutations of 4 objects out of 9 should be 3024 (9*8*7*6), so you should get 3024 arrays of 4

edit

function permute(level, permuted, used, original){

    if (level == 4) {
        hitterArray.push(permuted); //You don't need to create a copy here, but if performance is not an issue, you might want to do it, for clarity
    } else {
        for (var i = 0; i < original.length; i++) {
            if (!used[i]) {
                var newused = used.slice();
                var newpermuted = permuted.slice();

                newused[i] = true;

                newpermuted.push(original[i]);

                permute(level + 1, newpermuted, newused, original);

                //used[i] = false; //this won't be needed as you've just created a copy of the original one
            }
        }
    }
}

edited Jul 14, 2015 at 13:06

answered Jul 14, 2015 at 9:07

Joao Leal

5,5521 gold badge15 silver badges23 bronze badges

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

2 Comments

CQM Over a year ago

where exactly would I use array.slice, in the function calls?

Joao Leal Over a year ago

I think the best place is before making changes to the arrays, see my edit.

Collectives™ on Stack Overflow

Javascript recursion not functioning as expected

1 Answer 1

edit

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

edit

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related