这个递归数组排列函数在引擎盖下是如何工作的？

Question

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

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

这就是我迷路的地方。它似乎跳回拼接并将拼接 2 跳回 arr。在devTools中，我监视i，item，temp和arr。它说我以某种方式变成了 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 日志项，则从 ARR 中删除该元素并将其附加到项目中，因为下一个排列会重复出现，ARR 中少一个元素，在项目中多一个元素

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

当您处理这个问题时，请记住您有多个调用要在运行时堆栈上执行:第一个调用遍历item[0]的所有3个可能的选择；第二个遍历item[1]的两个可能选项，第三个获取剩余的元素，记录排列，并返回到第二个调用。每个调用实例维护其I、len和item的本地值。

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

堆栈：

>

doIt，i=0，len=1，item=3

doIt，i=0，len=2，item=2

doIt，i=0，len=3，item=1

< li>arr=[3]，temp=[1，2]

我们现在回到前面的调用#2，从堆栈中弹出调用#3。在这次通话中，我们刚刚结束了#3 doIt通话。我们跳到恢复点，将2拼接回arr，并迭代到循环的顶部。

将i递增到1，从arr中选择值3，留下temp=[1,3]和arr=2。重复做，另一个调用#3…

…它选择剩余的2，记录解[1，3，2]，将2放回arr，并返回调用#2。

Call #2将3拼接回arr，进行迭代，将I增加到2，nhas现在耗尽了它的for循环。它将1重新拼接到arr上，并返回到调用#1。

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

这足够让你明白这个想法了吗？