三个傻瓜都能看懂的计算全排列方法

作为前端开发人员，具备一定的计算机基础和数学知识不仅有助于解决编写代码中的问题，还可以提高代码的质量。其中计算全排列是常见的需求之一，并且在业务场景中经常会用到。那么，如何计算全排列呢？

什么是全排列？

全排列指从给出的元素集合中任选一个起点，然后按照某种特定的顺序将其余元素递归地放入空挡中，直到数组被填满为止，所有得到的排列组合形式就是这组元素的全排列。例如，如果给定一个长度为3的数组{1、2、3}，那么它的全排列为：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

递归法实现全排列

递归法是实现全排列最常见的方法之一，常用于小规模全排列计算。算法思路是：将数组分成已知部分（第一个元素）与未知部分（除第一个元素外的数组），每次递归时取未知部分的第一个元素到已知部分中，再将后面的元素进行全排列，直至递归结束。

代码实现如下：

function getPermutation(arr) {
    const result = [];
    if (arr.length === 1) {
        return [arr];
    } else {
        for (let i = 0; i < arr.length; i++) {
            let first = arr[i];
            let left = arr.slice(0, i).concat(arr.slice(i + 1));
            let rest = getAllPermutation(left);
            for (let j = 0; j < rest.length; j++) {
                let next = [first].concat(rest[j]);
                result.push(next);
            }
        }
    }
    return result;
}

字典序法实现全排列

字典序法是指按照某种规则进行遍历，在全排列的计算中也常常用到。算法思路是：首先将要进行排序的数组按从小到大的顺序排序，然后做以下操作：

1. 从数组末尾开始查找一个数对 （i，j），使得 A[i] < A[j]；
2. 如果查找失败则执行 step4，否则继续执行 step3；
3. 在第 (i, n) 中寻找最小数K,满足 A[k] > A[i], 将 A[i] 和 A[k] 交换位置，并将 A[j:n] 排序；
4. 此时生成了一个全排列，算法结束。

代码实现如下：

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function reverse(arr, start, end) {
    while (start < end) {
        swap(arr, start++, end--);
    }
}

function getPermutation(arr) {
    const result = [];
    let len = arr.length;
    arr.sort((a, b) => a - b);
    result.push([...arr]);
    while (true) {
        let i = len - 2,
            j = len - 1,
            k = len - 1;
        while (i >= 0 && arr[i] >= arr[j]) {
            i--;
            j--;
        }
        if (i === -1) {
            break;
        }
        while (k >= 0 && arr[k] <= arr[i]) {
            k--;
        }
        swap(arr, i, k);
        reverse(arr, j, len - 1);
        result.push([...arr]);
    }
    return result;
}

Heap算法实现全排列

Heap算法是一种使用交换来产生所有排列的算法。它相对于递归法而言更加高效，可以处理大规模的全排列问题。算法思路是：从左到右依次交换每一个元素和第一个元素，同时递归处理后面的元素，直到数组长度为1为止。

代码实现如下：

function getPermutation(arr) {
    const result = [];
    function permute(n, arrInput) {
        if (n === 1) {
            result.push([...arrInput]);
        } else {
            for (let i = 0; i < n - 1; i++) {
                permute(n - 1, arrInput);
                if (n % 2 === 0) {
                    [arrInput[i], arrInput[n - 1]] = [arrInput[n - 1], arrInput[i]];
                } else {
                   [arrInput[0], arrInput[n - 1]] = [arrInput[n - 1], arrInput[0]]; 
                }
            }
            permute(n - 1, arrInput);
        }
    }
    permute(arr.length, arr);
    return result;
}

总结

以上介绍了三种常见的计算全排列方法，根据不同的需求可选择最合适的方法进行计算。

• 递归法是最简单、易懂的方法，在小规模数据的情况下运行速度较快；
• 字典序法比起递归法有了明显的优化，能够很好地应对中等规模的数据，同时代码实现也相对简单；
• Heap算法实现全排列速度最快，在处理大规模排列问题时表现出了优越的性能和不错的可读性。

在实际应用中，可以根据需求选择不同的算法实现。而个人建议是，掌握多种计算全排列的方法，有助于提高算法思维、解决实际问题，并且为将来的职业发展打下更坚实的基础。

更多题目

juejin.cn/column/7201…