Heap's Algorithm Walk-Through

Question

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 1

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.