Edson Edson - 25 days ago 9
Javascript Question

Heap's Algorithm Walk-Through

So, I'm learning recursion, and I'm working on a coding challenge that requires all variations of elements in an array.

I was pointed to Heap's algorithm and this is what I've drawn up so far in JavaScript.

function generate(n, array) {
if (n == 1) {
return array;
}
else {
for (var i = 0; i < n - 1; i++) {
generate(n - 1, array);
if (n % 2 == 0) {
swap(array[i], array[n - 1]);
}
else {
swap(array[0], array[n - 1]);
}
}
generate(n - 1, array);
}
}


Please ignore the fact that I haven't translated the "swap" instances to JavaScript.

I'm a bit unsure as how to exactly walk-through the recursive part of this algorithm.

Say I have the array: [A,B,C,D,E]. I believe that the arguments I would pass into the outer function would be:

generate(5, [A,B,C,D,E]);


In this case, n is not equal to 1, so I would move on to the "else" portion.
I encounter the for-loop and, because n is 5, it executes.

Next: The function calls itself, but this time the arguments are:

generate(4, [A,B,C,D,E]);


This is where my confusion begins:

As I'm walking through this, do I move on to the "if"/"else" conditions
or do I (after the recursive call) go back up to the very start of the outer function?

Update

Below is the totally translated JavaScript version of Heap's algorithm.

function generate(n, array) {
//console.log("ENTER", n, array)

if (n == 1) {

console.log(array);
}

else {

for (var i = 0; i < n - 1; i++) {
//console.log("RECUR", n-1, array)


generate(n - 1, array);

if (n % 2 == 0) {
//console.log("SWAP ", n, array)

var one = array[i];
var two = array[n - 1];

array[i] = two;

array[n - 1] = one;

//swap(array[i], array[n - 1]);
}

else {
//console.log("SWAP ", 0, n-1)

var first = array[0];
var second = array[n - 1];

array[0] = second;

array[n - 1] = first;


//swap(array[0], array[n - 1]);
}
//console.log("array", array)
}

//console.log("RECUR 2", n-1, array)

generate(n - 1, array);
}

//console.log("LEAVE", n, array)


}

I was walking through it on paper until I reached a point where I got a repeat, [A,B,C,D] again.

Thinking I messed up, I decided to implement Prune's suggestion of console outputs to see what was happening in the console and it was helpful.

After fixing a small error, it's working just fine now.

Thanks to everyone that helped!

Answer

My canonical answer at this point is, if you're having trouble walking through the algorithm on paper, don't! Make the computer do it for you. Insert a bunch of console.log commands to trace the execution. Trace the entry and exit of each routine and call, including useful values.

function generate(n, array) {
    console.log("ENTER", n, array)
    if (n == 1) {
        return array;
    }
    else {
        for (var i = 0; i < n - 1; i++) {
            console.log("RECUR", n-1, array)
            generate(n - 1, array);
            if (n % 2 !== 0) {
                console.log("SWAP ", n, array)
                swap(array[i], array[n - 1]);
            }
            else {
                console.log("SWAP ", 0, n-1)
                swap(array[0], array[n - 1]);
            }
            console.log("array", array)
        }
        console.log("RECUR 2", n-1, array)
        generate(n - 1, array);
    }
    console.log("LEAVE", n, array)
}

This will give you a lovely execution trace. For even greater readability, indent each line of output 2*(5-n) spaces.