全排列问题

问题描述：生成n个互异元素a1,a2…an的全排列（所有排列）。

全排列的核心思想是：

1. 确定一个元素： 从待排列的元素中选择一个元素，作为当前排列的第一个元素。
2. 排列剩余元素： 对剩余的元素进行全排列。
3. 组合： 将第一个元素和剩余元素的全排列组合起来，形成一个完整的排列。
4. 重复： 对每个可能的第一个元素重复上述步骤。

const array = ["A", "B", "C", "D", "E"];
function generateFullArrays(arr) {
    if (arr.length === 0) {
        return [[]]; // 一个空数组的全排列是包含一个空数组的数组
    }
    if (arr.length === 1) {
        return [[arr[0]]]; // 只有一个元素，全排列就是包含该元素的数组
    }
    const result = []; // 存储所有生成的全排列
    // 递归情况：遍历数组中的每一个元素，将其作为当前排列的第一个元素
    for (let i = 0; i < arr.length; i++) {
        const currentElement = arr[i]; // 选择当前元素作为第一个元素
 
        // 构建剩余元素数组：除了 currentElement 之外的所有元素
        // 使用 slice() 避免修改原数组
        const remainingElements = arr.slice(0, i).concat(arr.slice(i + 1));
 
        // 递归地生成剩余元素的全排列
        const permutationsOfRemaining = generateFullArrays(remainingElements);
 
        // 将当前元素与剩余元素的全排列进行组合
        for (let j = 0; j < permutationsOfRemaining.length; j++) {
            // 将 currentElement 放在每个剩余元素排列的前面
            result.push([currentElement].concat(permutationsOfRemaining[j]));
        }
    }
    return result;
}

回溯算法实现

 
/* 回溯算法：全排列 I */
function backtrack(state, choices, selected, res) {
    // 当状态长度等于元素数量时，记录解
    if (state.length === choices.length) {
        res.push([...state]);
        return;
    }
    // 遍历所有选择
    choices.forEach((choice, i) => {
        // 剪枝：不允许重复选择元素
        if (!selected[i]) {
            // 尝试：做出选择，更新状态
            selected[i] = true;
            state.push(choice);
            // 进行下一轮选择
            backtrack(state, choices, selected, res);
            // 回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.pop();
        }
    });
}
 
/* 全排列 I */
function permutationsI(nums) {
    const res = [];
    backtrack([], nums, Array(nums.length).fill(false), res);
    return res;
}
 

reference