js数组实现全排列

使用递归方法实现全排列

递归方法是实现全排列的经典方式，通过不断交换数组元素的位置来生成所有可能的排列组合。

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

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

    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];
      backtrack(start + 1);
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  }

  backtrack(0);
  return result;
}

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

使用堆算法实现全排列

堆算法是一种非递归的全排列生成方法，效率较高且不需要额外空间。

function heapPermutation(nums) {
  const result = [];
  const n = nums.length;

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

    generate(k - 1);

    for (let i = 0; i < k - 1; i++) {
      if (k % 2 === 0) {
        [nums[i], nums[k - 1]] = [nums[k - 1], nums[i]];
      } else {
        [nums[0], nums[k - 1]] = [nums[k - 1], nums[0]];
      }
      generate(k - 1);
    }
  }

  generate(n);
  return result;
}

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

使用库函数简化实现

现代JavaScript提供了更简洁的实现方式，可以结合扩展运算符和reduce方法。

function permutations(arr) {
  return arr.reduce((acc, val) => 
    acc.flatMap(perm => 
      [...Array(perm.length + 1)].map((_, i) => 
        [...perm.slice(0, i), val, ...perm.slice(i)]
      )
    ), [[]]
  ).filter(perm => perm.length === arr.length);
}

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

处理包含重复元素的情况

当数组中存在重复元素时，需要额外处理以避免生成重复的排列。

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

  function backtrack(temp, used) {
    if (temp.length === nums.length) {
      result.push([...temp]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) continue;
      used[i] = true;
      temp.push(nums[i]);
      backtrack(temp, used);
      used[i] = false;
      temp.pop();
    }
  }

  backtrack([], Array(nums.length).fill(false));
  return result;
}

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

性能优化建议

对于大型数组，全排列的计算量会急剧增加。可以考虑使用生成器函数来按需产生排列，而不是一次性生成所有结果。

function* permuteGenerator(arr) {
  if (arr.length <= 1) yield arr;
  else {
    const [first, ...rest] = arr;
    for (const perm of permuteGenerator(rest)) {
      for (let i = 0; i <= perm.length; i++) {
        yield [...perm.slice(0, i), first, ...perm.slice(i)];
      }
    }
  }
}

// 示例用法
for (const perm of permuteGenerator([1, 2, 3])) {
  console.log(perm);
}

这些方法涵盖了从基础到进阶的多种实现方式，可以根据具体需求选择最适合的方案。递归方法直观易懂，堆算法效率较高，而生成器函数适合处理大规模数据。对于包含重复元素的数组，需要特别注意去重处理。