堆的算法演练

Question

因此，我正在学习递归，并且正在应对一项编码挑战，该挑战需要数组中元素的所有变体。

我被指向 Heap's algorithm，这就是我目前在 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);
    }
}

请忽略我没有将 "swap" 个实例翻译成 JavaScript 的事实。

我有点不确定，因为 如何准确地遍历该算法的递归部分。

假设我有数组：[A,B,C,D,E]。我相信我将传递给外部函数的参数是：

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

在这种情况下，n 不等于 1，因此我将转到 "else" 部分。我遇到了 for 循环，因为 n 是 5，所以它执行了。

接下来：函数调用自身，但这次的参数是：

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

这就是我开始困惑的地方:

当我完成这个过程时，我是否会转到 "if"/"else" 条件还是我（在递归调用之后）返回到外部函数的开头？

更新

下面是完全翻译的 JavaScript 版本的 Heap 算法。

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)

}

我在纸上遍历它，直到我得到一个重复的点，再次 [A,B,C,D]。

以为我搞砸了，我决定实施 Prune 关于控制台输出的建议，以查看控制台中发生的情况，这很有帮助。

修复了一个小错误后，现在可以正常工作了。

感谢所有帮助过的人！

Answer 1

此时我的规范回答是，如果您在纸上遍历算法时遇到困难，不要！让电脑为你做。插入一堆console.log命令来跟踪执行。跟踪每个例程和调用的进入和退出，包括有用的值。

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)
}

这会给你一个可爱的执行轨迹。为了提高可读性，将每行输出缩进 2*(5-n) 个空格。

Answer 2

让我列举一下你的台词，这样我们就可以更容易地参考它们（见下文）

你从 generate(5, [A,B,C,D,E]); 走到了 generate(4, [A,B,C,D,E]);（在第 7 行），然后你第二次进入 generate，没有完成你的第一次调用，所以你暂停到第一个电话并开始与第二个电话一起走路

现在（第二次调用）n=4 所以你再次到达第 7 行，但这次第三次调用 generate(3, [A,B,C,D,E]) 开始（没有完成之前的调用）

第 4 次调用也是如此 generate(2, ...)，但第 5 次调用 generate(1, ...) 情况开始发生变化

在第 5 次调用 n=1 中，因此第 2 行的条件为真并返回 array，我们回到我们来自的地方，即第 7 行的第 4 次调用，其中返回的数组什么都不做（它没有分配或任何东西）然后我们在第 4 次调用时到达第 8 行（第一次），n=2 因此第二个 swap 发生并且 i 递增，回到第 7 行，我们再次调用 generate(1, ...) 以获得相同的结果......等等

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. }

堆的算法演练

Heap's Algorithm Walk-Through

javascript

algorithm

recursion

heaps-algorithm