全排列就是将给定序列的所有排列方式找出。

递归解法

有重复

如下这种方式使用递归，将整组数中的所有的数分别与第一个数交换swap(start,i);，这样就总是在处理后n-1个全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function perm(list,start,end){
  if(start>end){
    console.log(list);
  }else{
    for(let i=start;i<=end;i++){
      swap(list,start,i);
      perm(list,start+1,end);
      swap(list,start,i)
    }
  }
}

function swap(list,i,j){
  let tmp=list[i];
  list[i]=list[j];
  list[j]=tmp;
}
let list=[1,2,3,4,5];
perm(list,0,4);

去重复

那么在这种递归的方法中，如何去掉重复的全排列呢。

先举个例子：1，2，2

  1. 在这个数组中将第一个数与第二个数交换得到2，1，2，将第一个与第三个交换得到2，2，1

  2. 然后将2，1，2中的第二个与第三个交换2，2，1，额，，，发生了重复，咱们需要转换思路了。

  3. 重新梳理。将第一个数与第二个数交换得到2，1，2，然后发现第二个数与第三个数相同，于是第一个数不再与第三个数交换。

  4. 再考虑2，1，2，将第二个数与第三个数交换得到2，2，1.此时全排列完成。

这样我们也得到了在全排列中去掉重复项的规则：去重的全排列就是从第一个数字起，每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时，要求[i,j]中没有与第j个数相等的数。

新添加了一个isSwap函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function perm(list,start,end){
  if(start>end){
    console.log(list);
  }else{
    for(let i=start;i<=end;i++){
      if(isSwap(list, start, i)){
        swap(list,start,i);
        perm(list,start+1,end);
        swap(list,start,i)
      }
    }
  }
}
function isSwap(list, start,end){
  for(let i=start;i<end;i++){
    if(list[i]===list[end]){
      return false;
    }
  }
  return true;
}
function swap(list,i,j){
  let tmp=list[i];
  list[i]=list[j];
  list[j]=tmp;
}
let list=[1,2,3,4,5];
perm(list,0,4);

字典排序法

全排列的另外一种方法是字典排序法。

  1. 字典排序法，就是在数组中，从后往前找，找到第一个非递增数比如1，2，4，3中2就是从前往后第一个非递增数。

  2. 然后再次从后往前找，找到第一个大于2的数，在这里就是3，交换2和3，数组变成1，3，4，2。

  3. 最后再逆置3后面的数即1，3，2，4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function main(list){
  list.sort((a,b)=>{
    return a-b;
  })
  console.log(list);
  while(perm(list)){
    console.log(list);
  }
}
function perm(list){
  let index;
//从后往前找，找到第一个非递增数
  for(let i=list.length-2;i>=0;i--){
    if(list[i]<list[i+1]){
      index=i;
      break;
    } else if (i === 0) { //若没找到，说明当前序列已经是最大字典序了
      return false;
    }
  }
//从后往前找，找到第一个大于index位置上的数
  for(let i=list.length-1;i>=index;i--){
    if(list[i]>list[index]){
      swap(list, i, index);
      reverse(list, index+1);
      break;
    }
  }
  return true;
}
function swap(list,i,j){
  let tmp=list[i];
  list[i]=list[j];
  list[j]=tmp;
}
function reverse(list, start){
  let end = list.length-1;
  while(start<end){
    swap(list,start,end);
    start++;
    end--;
  }
}