js数组实现全排列
全排列的概念
全排列是指将一组元素的所有可能的排列方式列举出来。例如，数组 [1, 2, 3] 的全排列包括 [1, 2, 3]、[1, 3, 2]、[2, 1, 3] 等共 6 种排列。
递归方法实现全排列
递归是解决全排列问题的常见方法，通过不断交换数组元素的位置生成所有可能的排列。
function permute(nums) {
const result = [];
function backtrack(start) {
if (start === nums.length) {
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;
}
const arr = [1, 2, 3];
console.log(permute(arr));堆算法实现全排列
堆算法（Heap's Algorithm）是一种高效的全排列生成算法，通过减少交换次数提高性能。
function heapPermute(nums) {
const result = [];
function generate(n) {
if (n === 1) {
result.push([...nums]);
return;
}
for (let i = 0; i < n; i++) {
generate(n - 1);
if (n % 2 === 0) {
[nums[i], nums[n - 1]] = [nums[n - 1], nums[i]]; // 偶数位置交换
} else {
[nums[0], nums[n - 1]] = [nums[n - 1], nums[0]]; // 奇数位置交换
}
}
}
generate(nums.length);
return result;
}
const arr = [1, 2, 3];
console.log(heapPermute(arr));使用库函数生成全排列
某些 JavaScript 库（如 Lodash）提供了生成全排列的工具函数，可以直接调用。
const _ = require('lodash');
const arr = [1, 2, 3];
const permutations = _.permutations(arr);
console.log(permutations);注意事项
- 递归方法的时间复杂度为 O(n!)，适合小规模数据。
- 堆算法的性能优于普通递归方法，适合中等规模数据。
- 使用库函数可以简化代码，但需引入外部依赖。
