JavaScript 数组全排列算法改进：输出子数组结果

JavaScript 数组全排列算法改进：输出子数组结果

本文将改进一个常见的 JavaScript 数组全排列算法，使其不仅能输出全排列结果，还能输出所有子数组的结果。

原始算法

const permute = (arr) => arr.length === 1 ? [arr] : arr.flatMap((val, i) => permute([...arr.slice(0, i), ...arr.slice(i + 1)]).map((perm) => [val, ...perm]));

该算法使用递归和 flatMap 方法来生成所有可能的排列。但是，它只输出全排列结果，没有输出子数组结果。

改进后的算法

为了输出子数组结果，可以在递归的基本情况中加入一个额外的判断条件。以下是改进后的函数：

const permute = (arr) => {
  if (arr.length === 1) {
    return [arr];
  } else {
    let result = [];
    arr.forEach((val, i) => {
      const subArr = [...arr.slice(0, i), ...arr.slice(i + 1)];
      const subPerms = permute(subArr);
      subPerms.forEach((perm) => {
        result.push([val, ...perm]);
      });
      result.push(subArr);
    });
    return result;
  }
};

工作原理

改进后的算法在递归的基本情况下，不仅返回单元素数组本身，还返回一个空数组。这样，在递归过程中，每次都会生成子数组的结果，并添加到最终结果数组中。

示例

对于输入 [1, 2, 3]，改进后的算法将输出：

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], [1, 2], [2, 1], [1, 3], [3, 1], [2, 3], [3, 2]]

总结

通过简单的改进，我们就可以让 JavaScript 数组全排列算法输出子数组结果，从而更加灵活地处理各种情况。