JavaScript排列算法递归调用中splice方法运行逻辑疑问

你提供的排列实现代码如下：

function permutator(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return results;
  }

  return permute(inputArr);
}

核心方法splice的作用 #

首先明确Array.splice()是原地修改数组的方法，语法为arr.splice(起始下标, 删除数量, [插入的元素])，返回值是被删除元素组成的数组。
你标注疑问的两处splice作用分别为：

• cur = arr.splice(i, 1)：从当前数组的下标i位置删除1个元素，将被删除的元素存入cur变量，此时原数组会移除该元素。
• arr.splice(i, 0, cur[0])：这是回溯操作的核心，作用是将刚才删除的元素插回原数组的i位置，将数组恢复到本次循环开始前的状态，保证下一次i迭代时处理的是完整的原始数组。

递归运行逻辑说明 #

你的理解偏差核心是忽略了回溯步骤对数组的还原操作，我们以输入数组[a,b,c]为例简化演示流程：

1. 顶层调用permute([a,b,c], [])，数组初始状态为[a,b,c]，循环i从0到2：
   • 当i=0时：
     • 执行splice(0,1)，cur为[a]，数组变为[b,c]
     • 递归调用下一层permute([b,c], [a])，该层的循环会生成所有a开头的排列：[a,b,c]、[a,c,b]
     • 递归结束后执行splice(0,0,a)，数组还原为[a,b,c]
   • 当i=1时：
     • 执行splice(1,1)，cur为[b]，数组变为[a,c]
     • 递归调用下一层生成所有b开头的排列：[b,a,c]、[b,c,a]
     • 递归结束后执行splice(1,0,b)，数组还原为[a,b,c]
   • 当i=2时：
     • 执行splice(2,1)，cur为[c]，数组变为[a,b]
     • 递归调用下一层生成所有c开头的排列：[c,a,b]、[c,b,a]
     • 递归结束后执行splice(2,0,c)，数组还原为[a,b,c]
2. 所有排列生成完成后返回结果数组。

预期结果出错的原因 #

你认为输入[0,1,2,3,4,5,6,7]时cur会依次为0、2、4、6，是默认每次循环后数组会永久保留删除元素的状态，但实际每次循环末尾都执行了回溯插回操作，每次迭代i对应的都是初始的完整数组，所以cur会依次为0、1、2、3、4、5、6、7，和你预期不符。

内容的提问来源于stack exchange，提问作者med azzouzi