js数组实现全排列

全排列的概念

全排列是指从给定数组中取出所有元素进行排列组合，生成所有可能的顺序。对于长度为n的数组，全排列共有n!种可能。

递归实现方法

递归是解决全排列问题的经典方法。通过固定一个元素，递归生成剩余元素的全排列，再将固定的元素与递归结果拼接。

function permute(nums) {
  const result = [];

  function backtrack(current, remaining) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      const newRemaining = remaining.slice(0, i).concat(remaining.slice(i + 1));
      backtrack(current, newRemaining);
      current.pop();
    }
  }

  backtrack([], nums);
  return result;
}

// 示例用法
console.log(permute([1, 2, 3]));

交换法实现

通过交换数组元素的位置来生成排列，减少内存消耗。

function permuteSwap(nums) {
  const result = [];

  function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }

  function generate(start) {
    if (start === nums.length - 1) {
      result.push([...nums]);
      return;
    }

    for (let i = start; i < nums.length; i++) {
      swap(nums, start, i);
      generate(start + 1);
      swap(nums, start, i);
    }
  }

  generate(0);
  return result;
}

使用堆算法

堆算法是一种非递归的全排列生成方法，效率较高。

function heapPermute(nums) {
  const result = [];
  const n = nums.length;
  const c = new Array(n).fill(0);

  result.push([...nums]);

  let i = 0;
  while (i < n) {
    if (c[i] < i) {
      if (i % 2 === 0) {
        [nums[0], nums[i]] = [nums[i], nums[0]];
      } else {
        [nums[c[i]], nums[i]] = [nums[i], nums[c[i]]];
      }
      result.push([...nums]);
      c[i]++;
      i = 0;
    } else {
      c[i] = 0;
      i++;
    }
  }

  return result;
}

使用库函数

现代JavaScript引擎提供了更简洁的实现方式。

// 使用生成器函数
function* permuteGenerator(arr) {
  if (arr.length === 1) yield arr;

  for (let i = 0; i < arr.length; i++) {
    const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    for (const p of permuteGenerator(rest)) {
      yield [arr[i], ...p];
    }
  }
}

// 转换为数组
const permutations = [...permuteGenerator([1, 2, 3])];
console.log(permutations);

性能考虑

对于大型数组，递归方法可能会导致堆栈溢出。非递归方法如堆算法更适合处理大量数据。在实际应用中，应根据数据规模选择合适的方法。

去重处理

当数组包含重复元素时，需要额外处理以避免生成重复排列。

function permuteUnique(nums) {
  const result = [];
  nums.sort((a, b) => a - b);

  function backtrack(current, remaining) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      if (i > 0 && remaining[i] === remaining[i - 1]) continue;
      current.push(remaining[i]);
      const newRemaining = remaining.slice(0, i).concat(remaining.slice(i + 1));
      backtrack(current, newRemaining);
      current.pop();
    }
  }

  backtrack([], nums);
  return result;
}