如何获取数组元素的全排列组合？现有代码无法生成指定排列

原代码的逻辑是生成数组的幂集（所有非空子集），它通过二进制位标记是否包含数组中的元素，并且直接按原数组顺序拼接元素，所以只会得到像AB、ABC这类保持原元素顺序的结果，无法生成BA、BCAD这类改变元素顺序的排列。

要得到所有包含不同元素顺序的组合，本质是要生成数组的所有非空排列（包括长度1到n的所有排列）。可以通过回溯法实现，具体代码如下：

function getAllPermutations(arr) {
    const result = [];

    // 生成指定长度的排列
    function permute(current, remaining) {
        if (current.length > 0) {
            result.push(current.join(''));
        }
        for (let i = 0; i < remaining.length; i++) {
            // 选择当前元素，剩余元素排除当前元素后继续递归
            permute(
                [...current, remaining[i]],
                [...remaining.slice(0, i), ...remaining.slice(i + 1)]
            );
        }
    }

    permute([], arr);
    return result;
}

// 测试示例
const letters = ["A", "B", "C", "D"];
const allPermutations = getAllPermutations(letters);
console.log(allPermutations.join('\n'));

代码说明 #

• 外层函数getAllPermutations初始化结果数组，调用内部回溯函数permute
• permute函数接收两个参数：current是当前正在构建的排列，remaining是未使用的元素
• 每次递归时，只要current不为空，就将其转为字符串加入结果集
• 遍历remaining中的每个元素，将其加入current，同时从remaining中移除该元素，继续递归直到remaining为空

运行这段代码后，就能生成所有符合需求的结果，包括A、AB、AC、ABCD、B、BA、BCAD、BDCA等所有不同长度、不同顺序的排列组合。

内容的提问来源于stack exchange，提问作者Yusuf Göçer