全排列算法

参考资料

先上代码，实现非常简洁

/**
 * @description 给定字符串输出字符串中字母的全排列
 */
const input = ['a', 'b', 'c'];
const algorithm = (input) => {
    const result = [];
    const permutation = (arr, first = '') => {
        let beforeStr = first;
        arr.forEach((item) => {
            if (arr.length <= 1) {
                return result.push(beforeStr + item);
            }
            const extra = arr.filter((_item) => _item !== item);
            return permutation(extra, beforeStr + item);
        });
        return beforeStr;
    };
    permutation(input);
    return result;
};

console.log('input', input);
console.log('output', algorithm(input));

输出

image.png

主要思路

image.png

在此树中，每一个从树根到叶子节点的路径，就对应了集合A的一个排列。通过递归算法，每次将一个结果入结果集合，最终输出。