30天挑战数据结构和算法之全排列算法的递归实现

写这篇文章的时候不知道是30天内的第几天了，原本打算开始的数据结构学习也被搁浅了。业余时间主要还是在学习最短路径问题，没办法这是工作中最常遇到的问题，必须要搞清楚，可能后面就会轻松点了。

在使用穷举法解最短路径问题的时候，我看到一种使用全排列算法的实现方式，于是开始了对全排列算法的研究。这里给出全排列的定义

从n个元素中取出m个元素进行排列，当n=m时，这个排列被称为全排列

举个例子，比方说我要求数组[1,2,3]的全排列形式。那么最后的输出结果应该是

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,2,1]
[3,1,2]

换句话说，对于一个拥有m个不重复元素的数组，它的全排列一共有m!种形式。

那么如何使用计算机来实现全排列的算法呢？这里只考虑使用递归的方式实现。我是根据代码结果来反验证递归的正确性，下面来看看代码先

var fullyArranged = function (array, cursor) {
    if (cursor == array.length) {
        console.log(array)
    } else {
        for (var i = cursor; i < array.length; i++) {
            console.log("cursor = " + cursor + ", i = " + i);
            swap(array, cursor, i);
            fullyArranged(array, cursor + 1);
            swap(array, cursor, i);
        }
    }
}

var swap = function (array, i, j) {
    if (i == j) return;
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
    console.log("i = " + i + ", j = " + j);
}

fullyArranged([1, 2, 3], 0);

我大致解释一下这个递归算法的执行步骤。

// 第一步
cursor = 0, i = 0
cursor = 1, i = 1
cursor = 2, i = 2
// 输出原始数组 [ 1, 2, 3 ]

// 第二步
cursor = 1, i = 2
// 交换索引 i = 1, j = 2 的元素，即交换第二、第三个元素
cursor = 2, i = 2
// 输出 [ 1, 3, 2 ]

// 第三步
// 交换索引 i = 1, j = 2 的元素，即将上一步中的第二、第三个元素交换回来
// 此时数组变回初始数组 [ 1, 2, 3 ]

// 第四步
cursor = 0, i = 1
// 交换索引 i = 0, j = 1 的元素，即交换第一、第二个元素
cursor = 1, i = 1
cursor = 2, i = 2
// 输出 [ 2, 1, 3 ]

// 第五步
cursor = 1, i = 2
// 交换索引 i = 1, j = 2 的元素，即交换第二、第三个元素
cursor = 2, i = 2
// 输出 [ 2, 3, 1 ]

// 第六步
// 交换索引 i = 1, j = 2 的元素，即将上一步中的第二、第三个元素交换回来
// 输出 [ 2, 1, 3 ]

// 第七步
// 交换索引 i = 0, j = 1 的元素，即将第四步中的第一、第二个元素交换回来
// 此时数组变回了初始时的 [ 1, 2, 3 ]

// 第八步
cursor = 0, i = 2
// 交换索引 i = 0, j = 2 的元素，即交换第一、第三个元素
cursor = 1, i = 1
cursor = 2, i = 2
// 输出 [ 3, 2, 1 ]

// 第九步
cursor = 1, i = 2
// 交换索引 i = 1, j = 2 的元素，即交换第二、第三个元素
cursor = 2, i = 2
// 输出 [ 3, 1, 2 ]

// 第十步
// 交换回索引 i = 1, j = 2 的元素，即将上一步中的第二、第三个元素交换回来
// 输出 [ 3, 2, 1 ]

// 第十一步
// 交换回索引 i = 0, j = 2 的元素，即将第九步中的第一、第三个元素交换回来
// 此时数组变回了初始的 [ 1, 2, 3 ]

简单点来说，先把第一个元素的所有排列遍历，然后交换第二个元素到第一位将所有排列遍历，最后交换第三个元素到第一位将所有排列遍历。

这个算法中最重要的一点在于，对于交换过的元素，在结束完一次递归后要将元素交换回来，不然输出的结果会有重复。

我一直没弄明白一件事，递归算法的本质是什么。虽然我知道是栈操作，但短短几句代码，就实现了全排列效果，不得不佩服递归的神奇。如何把一句简简单单的描述用递归来实现，确实是一个不小的文章。

如果要排列四个元素以及更多，可以参考抽象成看三个元素的情况。