学习记录：js算法（八十三）：全排列
文章目录
- 全排列
- 思路一：回溯法
- 思路二：交换法
- 思路三：动态规划
- 思路四：迭代法
全排列
给定一个不含重复数字的数组
nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
思路一：回溯法
function permute(nums) {
const res = [];
const backtrack = (path, options) => {
if (options.length === 0) {
res.push([...path]);
return;
}
for (let i = 0; i < options.length; i++) {
// 选择
const num = options[i];
path.push(num);
// 构建下一层决策树
const nextOptions = [...options.slice(0, i), ...options.slice(i + 1)];
backtrack(path, nextOptions);
// 回溯
path.pop();
}
};
backtrack([], nums);
return res;
}
讲解
对于这道题，我们想要生成所有可能的全排列，可以看作是从剩余的未选数字中每次选择一个数字，直到所有数字都被选完为止。具体步骤如下：
- 初始化：创建一个空的路径数组
path来存储当前的排列，以及一个空的结果数组res来存储所有有效的排列。- 递归函数：定义一个递归函数
backtrack，它接受以下参数：
○ 当前路径path，
○ 剩余可选数字的集合options。- 基本结束条件：如果
options集合为空，这意味着我们已经选择了一个全排列，此时将当前路径path拷贝一份加入结果数组res，然后返回。- 回溯过程：对于
options集合中的每一个数字，执行以下操作：
○ 将当前数字添加到路径path中。
○ 从options集合中移除当前数字。
○ 递归调用backtrack函数，传递更新后的path和options。
○ 回溯，即将当前数字从路径path中移除，并将它放回·options·集合中。- 开始回溯：调用
backtrack函数，传入初始的path和options。- 返回结果：最后返回结果数组
res。
思路二：交换法
var permute = function (nums) {
const result = [];
const 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;
};
讲解
- 定义一个递归函数
backtrack(start)，其中start表示当前正在处理的元素的索引。- 如果
start等于数组的长度，说明已经生成了一个完整的排列，将其添加到结果集中。- 否则，遍历从
start到数组末尾的每个元素，对每个元素进行以下操作
○ 交换当前元素nums[start]和nums[i]（i从start到数组末尾）。
○ 调用递归函数backtrack(start + 1)继续处理下一个索引。
○ 在递归返回后，撤销交换，以恢复原数组的状态。- 运行示例
○ 假设输入数组为[1, 2, 3]，运行过程如下：
○ 初始状态：[1, 2, 3]
○ 第一次调用backtrack(0)，交换1和1，继续递归。
○ 进入backtrack(1)，交换2和2，继续递归。
○ 进入backtrack(2)，交换3和3，得到排列[1, 2, 3]，加入结果。
○ 撤销交换，返回到backtrack(1)，交换2和3，得到排列[1, 3, 2]，加入结果。
○ 撤销交换，返回到backtrack(0)，交换1和2，继续递归。
○ 依此类推，最终得到所有可能的排列。
思路三：动态规划
var permute = function (nums) {
const result = [];
const dp = (arr) => {
if (arr.length === 0) return [[]];
const res = [];
for (let i = 0; i < arr.length; i++) {
const remaining = arr.slice(0, i).concat(arr.slice(i + 1));
const perms = dp(remaining);
for (const perm of perms) {
res.push([arr[i], ...perm]);
}
}
return res;
};
return dp(nums);
};
讲解
- 定义一个递归函数
dp(arr)，该函数接受一个数组arr作为参数。- 如果
arr为空，返回一个包含空数组的数组[[]]，表示只有一种排列（空排列）。- 否则，遍历
arr中的每个元素，将当前元素arr[i]取出，并对剩余元素remaining进行递归调用，生成所有可能的排列。- 对于每个生成的排列，将当前元素插入到每个可能的位置，从而形成新的排列。
- 运行示例
○ 假设输入数组为[1, 2, 3]，运行过程如下：
○ 初始调用dp([1, 2, 3])。
○ 取出1，剩余元素为[2, 3]，递归调用dp([2, 3])。
○ 对[2, 3]，取出2，剩余为[3]，递归调用dp([3])。
○ 对[3]，返回[[3]]（基础情况）。
○ 得到排列[2, 3]和[3, 2]。
○ 将1插入到这两个排列中，得到[1, 2, 3]和[1, 3, 2]。
○ 继续处理2，取出2，剩余为[1, 3]，递归调用dp([1, 3])。
○ 依此类推，最终得到所有可能的排列。
思路四：迭代法
var permute = function (nums) {
let result = [[]];
for (const num of nums) {
const newResult = [];
for (const perm of result) {
for (let i = 0; i <= perm.length; i++) {
newResult.push([...perm.slice(0, i), num, ...perm.slice(i)]);
}
}
result = newResult;
}
return result;
};
讲解
- 初始化：
let result = [[]]，初始化结果数组result，开始时只有一个空排列。这是构建全排列的基础。
2.外层循环：
for (const num of nums)，遍历输入数组nums中的每个数字num。对于每个数字，我们都会生成新的排列。- 新结果数组：
const newResult = []，每次处理一个新数字时，创建一个新的结果数组newResult，用于存储包含当前数字的所有新排列。- 内层循环：
for (const perm of result)：遍历当前result中的每个排列perm。for (let i = 0; i <= perm.length; i++)：对于每个排列，尝试在不同的位置插入当前数字num。这里的i表示插入的位置，范围从0到perm.length（即在排列的开头和结尾也可以插入）。- 生成新排列：
newResult.push([...perm.slice(0, i), num, ...perm.slice(i)])：使用数组的slice方法生成新的排列。perm.slice(0, i)取出perm中从开头到i的元素，num是要插入的当前数字，perm.slice(i)取出perm中从i开始到结束的元素。通过展开运算符 ...将这些部分组合成一个新的数组，并将其添加到newResult中。- 更新结果：
result = newResult：在内层循环结束后，将result更新为newResult，以便在下一次迭代中使用新的排列集合。- 返回结果：
return result：最后返回包含所有全排列的数组result。