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

let me enumerate your lines, so we can refer to them easier (see below)

you walked from generate(5, [A,B,C,D,E]); up to generate(4, [A,B,C,D,E]); (at line 7) and then you entered generate for a 2nd time, without having finished your 1st call, so you put pause to the 1st call and start walking with the 2nd one

now (2nd call) n=4 so you get to line 7 again, but this time a 3rd call generate(3, [A,B,C,D,E]) starts (without finishing previous ones)

same goes for a 4th call generate(2, ...) and yet a 5th call generate(1, ...) which is when things start to change

in the 5th call n=1, so condition at line 2 evals true and array is returned, and we are back to where we came from, which is, the 4th call at line 7, where the returned array makes nothing (it is not assigned or anything) and then we reach line 8 (for the first time) while in the 4th call, n=2 therefore second swap happends and i is incremented, and back to line 7 we call again generate(1, ...) for the same result ... and so on

01. function generate(n, array) {
02.     if (n == 1) {
03.         return array;
04.     }
05.     else {
06.         for (var i = 0; i < n - 1; i++) {
07.             generate(n - 1, array);
08.             if (n % 2 !== 0) {
09.                 swap(array[i], array[n - 1]);
10.             }
11.            else {
12.                swap(array[0], array[n - 1]);
13.            }
14.        }
15.        generate(n - 1, array);
16.    }
17. }

Answer 2

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.