首页 文章

这个递归数组置换函数如何在引擎盖下工作？

提问于
浏览 次
3

此函数生成数组的排列 . 我已经用纸笔在开发工具中添加了断点，并且精心地逐步完成了每个函数调用，但我仍然不明白这是如何工作的 .

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

这是我迷路的地方 . 它似乎跳回到接头并拼接2回到arr . 在devTools中，我把 Watch 放在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]));

谢谢！

javascript arrays algorithm recursion permutation

1 回答

  • 4

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

    反过来为每个数组元素删除：从 arr 删除该元素并将其追加到 item 如果我们已经清空了 arr log 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 调用：第一个遍历项[0]的所有3个可能选项;第二个遍历项目[1]的2个可能选项，第三个选择剩余元素，记录排列，然后备份到第二个调用 . 每个调用实例都保持其本地值 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

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

    我们现在返回上一个呼叫，＃2，从堆栈弹出＃3呼叫 . 在这次通话中，我们刚刚从＃3 doIt 电话回来 . 我们跳转到恢复点，将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），为 temp 选择 2 ，然后我们开始以 2 开头的答案 .

    这足以让你获得这个想法吗？

    回复于

相关问题