javascript - 这个递归数组置换函数是如何工作的？

Question

此函数生成数组的排列。我已经拿起笔在纸上，在开发工具中放置断点，并煞费苦心地逐步完成每个函数调用，但我仍然不明白这是如何工作的。

具体来说，for 循环。一旦 do It 函数拼接出数组中的所有数字，它就会将临时数组的切片副本推送到答案数组中。然后它将 item 拼接到参数数组中，从 temp 数组中弹出相同的项目并返回 for 循环第一次迭代的答案。因此，在遍历数组一次后，答案 = [1,2,3] temp = [1,2] 和 arr =[3]。

这是我迷路的地方。好像跳回了splice，splice 2又回到了arr。在 devTools 中，我监视了 i、item、temp 和 arr。它说 i 不知何故变成了 1，即使在我们将 3 拼接回它后 arr 中只有一个项目。如果长度为 1 并且 for 循环指定它应该在 arr.length 处停止运行，它如何以某种方式跳回以将 2 拼接回数组？

如果我的措辞不连贯，我很抱歉。我今天花了很多时间来研究这个。

Tdlr。运行这个函数。在 do It 函数的 for 循环处放置一个断点。一旦数组为空并且我们返回答案，它如何将两个项目拼接回原始 arr。

function permute(arr) {
    var temp = [];
    var answer = [];

    function logResult() {
      answer.push(
        // make a copy of temp using .slice()
        // so we can continue to work with temp
        temp.slice()
      );
    }

    function doIt() {
      var i;
      var len;
      var item;

      for (i = 0, len = arr.length; i < len; i++) {
        // remove the item at index i
        item = arr.splice(i, 1)[0];
        // add that item to the array we're building up
        temp.push(item);
        if (arr.length) {
          // if there's still anything left in the array,
          // recurse over what's left
          doIt();
        } else {
          // otherwise, log the result and move on
          logResult();
        }
        // restore the item we removed at index i
        // and remove it from our temp array
        arr.splice(i, 0, item);
        temp.pop();  
      }
      return answer;
    }
  return doIt();
};

console.log(permute([1,2,3]));

谢谢!

Answer 1

一般来说，我不使用断点来跟踪这些，而是​​使用打印语句。 当我输入一个函数时，我会打印函数名称和参数值。当我离开时，我打印名称和退出(返回和状态)值。在这种情况下，我会在循环内做同样的事情。现在，让我们用更像英语的伪代码看看这个

依次对每个数组元素: 从 arr 中删除该元素并将其附加到 item 如果我们清空了 arr 将 item 记录为下一个排列 别的 在 arr 中少一个元素而在 item

中多一个元素的循环

// When we reach this point, we've exhausted all the permutations that
//   begin with the original state of **item**.
// Back up one element
take the chosen element from **item** and re-append it to **arr**.
// Go to the next loop iteration, which will move to the next element.

在完成此操作时，请记住您在运行时堆栈上多次调用 doIt:第一个遍历 item[0] 的所有 3 个可能选择；第二个遍历 item[1] 的 2 个可能选择，第三个获取剩余元素，记录排列，然后返回到第二个调用。每个调用实例都维护其本地值 i、len、 和 item。

对于您的具体问题，当前三个调用将 [1, 2, 3] 标识为解决方案时，状态如下所示:

堆栈:

1. doIt, i=0, len=1, item=3
2. doIt, i=0, len=2, item=2

3. doIt, i=0, len=3, item=1

   • arr=[3], temp=[1,2]

我们现在返回上一个调用，上面的 #2，从堆栈中弹出调用 #3。 在此调用中，我们刚刚从 #3 doIt 调用中返回。我们跳转到 restore 点，将 2 拼接回 arr，然后迭代到循环的顶部。

将i增加到1，从arr中选择值3，留下temp=[1,3]和arr=2。返回 doIt，另一个调用 #3 ...

... 选择剩余的 2，记录解决方案 [1, 3, 2]，将 2 放回 arr ，然后返回调用 #2。

调用 #2 拼接 3 回到 arr，迭代，将 i 递增到 2，nhas 现在用完了它的 for 循环。它将 1 拼接到 arr 并返回调用 #1。

我们现在有 temp=[]、arr=[1, 2, 3]，并且只有我们原来的 doIt 调用在堆栈上。它前进到下一个循环迭代 (i=1)，选择 2 for temp，我们从以 2 开头的答案开始。

这些追踪是否足以让您理解这个想法？