问题描述
给定一个任意数组，如何获得数组的全排列，例如[1,2,3]的全排列数组为[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]，即包含所有排列结果的长度为 \(A_{n}^{n}\) 的数组。
算法
function permute(arr) {
const result = [];
perm(arr, 0, result);
return result;
}
function perm(arr, start, result) {
if (start === arr.length) {
result.push([...arr]);
}
for (let i = start; i < arr.length; i++) {
[arr[start], arr[i]] = [arr[i], arr[start]];
perm(arr, start + 1, result);
[arr[start], arr[i]] = [arr[i], arr[start]];
}
}
代码展开
// arr=[1,2,3];start=0;result=[]
function perm(arr, start, result) {
if (start === arr.length) {
result.push([...arr]);
}
for (let i = start; i < arr.length; i++) {
// i=0时;start=0
[arr[0], arr[0]] = [arr[0], arr[0]];
// perm(arr, start + 1, result);
// arr=[1,2,3];start=1;result=[]
for (let i=1;i<3;i++) {
// i=1时
[arr[1], arr[1]] = [arr[1], arr[1]];
// perm(arr, start + 1, result);
// arr=[1,2,3];start=2;result=[];
for (let i=2;i<3;i++){
// i只能为2
[arr[2], arr[2]] = [arr[2], arr[2]];
// perm(arr, start + 1, result);
// arr=[1,2,3];start=3;result=[];
result.push([...[1,2,3]]); // arr=[1,2,3];start=3;result=[[1,2,3]];
[arr[2], arr[2]] = [arr[2], arr[2]];
}
[arr[1], arr[1]] = [arr[1], arr[1]]; // arr=[1,2,3];start=2;result=[[1,2,3]];
// i=2时
[arr[1], arr[2]] = [arr[2], arr[1]]; // arr=[1,3,2]
// perm(arr, start + 1, result);
// arr=[1,3,2];start=2;result=[[1,2,3]];
for (let i=2;i<3;i++){
// i只能为2，重复执行
result.push([...[1,3,2]]); // result=[[1,3,2];start=3;result=[[1,2,3],[1,3,2]];
}
[arr[1], arr[2]] = [arr[2], arr[1]]; // arr=[1,2,3];start=2;result=[[1,2,3],[1,3,2]];
}
[arr[0], arr[0]] = [arr[0], arr[0]]; // arr=[1,2,3];start=1;result=[[1,2,3],[1,3,2]];
// i=1时;start=0;
[arr[0], arr[1]] = [arr[1], arr[0]]; // arr=[2,1,3]
// perm(arr, start + 1, result);
// arr=[2,1,3];start=1;result=[[1,2,3],[1,3,2]];
for (let i=1;i<3;i++) {
// i=1时
[arr[1], arr[1]] = [arr[1], arr[1]];
// perm(arr, start + 1, result);
// arr=[2,1,3];start=2;result=[[1,2,3],[1,3,2]];
for(let i=2;i<3;i++){
// i只能为2
[arr[2], arr[2]] = [arr[2], arr[2]];
// perm(arr, start + 1, result);
// arr=[2,1,3];start=3;result=[[1,2,3],[1,3,2]];
result.push([...[2,1,3]]); // arr=[2,1,3];start=3;result=[[1,2,3],[1,3,2],[2,1,3]];
[arr[2], arr[2]] = [arr[2], arr[2]];
}
[arr[1], arr[1]] = [arr[1], arr[1]];
// i=2时
[arr[1], arr[2]] = [arr[2], arr[1]]; // arr=[2,3,1]
// perm(arr, start + 1, result);
// arr=[2,3,1];start=2;result=[[1,2,3],[1,3,2],[2,1,3]];
for (let i=2;i<3;i++){
//i只能为2
// perm(arr, start + 1, result);
// result = [[1,2,3],[1,3,2],[2,1,3],[2,3,1]];
}
[arr[1], arr[2]] = [arr[2], arr[1]]; // arr=[2,1,3]
}
[arr[0], arr[1]] = [arr[1], arr[0]]; // arr=[1,2,3]
// 执行完后result=[[1,2,3],[1,3,2],[2,1,3],[2,3,1]];
// i=2时;start=0
[arr[0], arr[2]] = [arr[2], arr[0]]; // arr=[3,2,1]
// ...
// 执行完后result=[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]];
}
}
解释
现在总共有n个数，从1到n，即arr=[1,2,3,...,n-1,n]，交换流程如下：
- 数1开始交换，先和自己交换，数组不变，但要等数2、数3、...、数n-1、数n交换完成，自己才算交换完成。一直推到最后一个数身上，最后一个数和自己交换，数组不变。全排列数组增加原数组
arr为第一个元素。结果长度为1!。 - 前面数的交换依赖后面数的交换，此时看数n-1，数n-1和数n交换，得到新
item=[1,2,...,n-2,n,n-1]，本轮数n-1交换完成。结果长度为2!。 - 数n-2开始交换，依次和n-1、n交换，和n-1交换后，n-1的还有自己的交换,即
[n-1,n-2,n]、[n-1,n,n-2]、[n,n-1,n-2]、[n,n-2,n-1]，实际是后3个数的全排列，去掉已经出现的结果，所以结果长度为3!。 - 依次类推，数
i交换后结果长度为(n-i+1)!。一直到数2交换完后，结果长度为(n-1)!，至此，数1后面每个数的交换都完成，说明数1和自己的交换完成。 - 数1和自己的交换完成后，数1和数2交换，新数组执行同样的流程，数2、数3、...、数n-1、数n依次执行交换。每轮结果长度增加
(n-1)! - 数1和数3、...、数n交换，最后结果总长度为
n*(n-1)!=n!。