js实现排列
排列算法实现（JavaScript）
排列是指从一组元素中按照一定顺序选取部分或全部元素进行排列组合。以下是几种常见的排列实现方法：
1. 全排列（递归法）
function permute(nums) {
let result = [];
const backtrack = (path, remaining) => {
if (remaining.length === 0) {
result.push([...path]);
return;
}
for (let i = 0; i < remaining.length; i++) {
path.push(remaining[i]);
backtrack(
path,
remaining.slice(0, i).concat(remaining.slice(i + 1))
);
path.pop();
}
};
backtrack([], nums);
return result;
}
// 示例
console.log(permute([1, 2, 3]));2. 全排列（交换法）
function permuteSwap(nums) {
const result = [];
const swap = (arr, i, j) => {
[arr[i], arr[j]] = [arr[j], arr[i]];
};
const generate = (start, arr) => {
if (start === arr.length - 1) {
result.push([...arr]);
return;
}
for (let i = start; i < arr.length; i++) {
swap(arr, start, i);
generate(start + 1, arr);
swap(arr, start, i);
}
};
generate(0, nums);
return result;
}
// 示例
console.log(permuteSwap([1, 2, 3]));3. 部分排列（从n个元素中取k个）
function partialPermute(nums, k) {
const result = [];
const backtrack = (path, remaining) => {
if (path.length === k) {
result.push([...path]);
return;
}
for (let i = 0; i < remaining.length; i++) {
path.push(remaining[i]);
backtrack(
path,
remaining.slice(0, i).concat(remaining.slice(i + 1))
);
path.pop();
}
};
backtrack([], nums);
return result;
}
// 示例
console.log(partialPermute([1, 2, 3, 4], 2));4. 去重排列（含重复元素）
function permuteUnique(nums) {
const result = [];
nums.sort((a, b) => a - b);
const backtrack = (path, used) => {
if (path.length === nums.length) {
result.push([...path]);
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;
path.push(nums[i]);
backtrack(path, used);
path.pop();
used[i] = false;
}
};
backtrack([], new Array(nums.length).fill(false));
return result;
}
// 示例
console.log(permuteUnique([1, 1, 2]));性能优化建议
1. 记忆化搜索 对于包含重复元素的排列问题，可以结合排序和记忆化技术来优化性能。
2. 迭代法替代递归 对于大规模数据，可以考虑使用堆算法（Heap's algorithm）的迭代实现来避免递归栈溢出。
3. 位运算优化 当元素数量较少（n ≤ 32）时，可以使用位掩码来表示元素的选择状态。
应用场景
- 密码破解中的暴力尝试
- 游戏中的关卡组合生成
- 数据分析中的参数排列组合
- 测试用例的自动化生成
以上实现涵盖了排列问题的常见场景，可根据具体需求选择合适的方法。递归法代码简洁但可能有栈深度限制，交换法则更节省空间但稍难理解。
