共计 4509 个字符，预计需要花费 12 分钟才能阅读完成。
什么是全排列？从 n 个不同元素中任取 m（m≤n）个元素，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一个排列。当 m = n 时所有的排列情况叫全排列。那么 ABC 的全排列有哪些？根据定义得到：ABCACBBACBCACABCBA
如何通过程序求解？方法一：暴力法，为什么是暴力法？因为暴力是机器唯一听得懂的语言。如何暴力？对一个空的字符串添加字母，添加三次，这个字母是 ABC 这三个中的一个。每添加完三个字母后，也就是得到一个排列以后，我们要检查这是不是个有效的排列。如果是就输出，否则跳过。有效的排列是指什么？是排列的所有数字都不相同，这里我使用双重循环来判断。这个判断函数复杂度较高为 O(N²)，但是容易理解，所以目前就先不使用更高效的算法。
java 代码：
public class Main {
public static void main(String[] args) throws Exception{
// 等待求解的全排列集合
char[]num = new char[]{‘A’,’B’,’C’};
for(int i = 0;i < num.length;i++)
for (int j = 0;j < num.length;j++)
for (int k = 0;k < num.length;k++)
{
char[]temp = new char[3];
temp[0] = num[i];
temp[1] = num[j];
temp[2] = num[k];
if(is_Legal(temp))
System.out.println(temp);
}
}
static boolean is_Legal(char[]temp)
{
for(int i = 0;i < temp.length;i++)
for(int j = i+1;j < temp.length;j++)
if(temp[i] == temp[j])
return false;
return true;
}
}
可以看到，通过 3 个 for 循环，不断填充候选答案的第 0 项，第 1 项，第 2 项。这样可以产生所有的候选答案，然后通过对每个候选答案判断是否合法来选择输出与否。
不过这里产生了两个问题。1：如果现在求的全排列不是 3 个数，而是 10 个数甚至 20 个数，那怎么办？要写十多个 for 循环？这样岂不是要累死。2：是否有必要产生所有的候选答案？换句话说，有些候选答案在产生过程中就已经是不合法的了，那么我们还有必要将这个候选答案完全“填充”吗(为什么要加深 ” 填充 ”？因为很重要！)？比如说 AAB 这个候选答案，在产生 AA 的时候就已经不合法了（不管第三个数填什么都是非法的）。
第一个问题，实际上是代码编写技巧的问题，比较容易解决，使用模板即可。那我们先来解决第一个问题！Let’s start！
我们发现，每个 for 循环做的事情，就是填充候选答案向量的某个位置，并且是固定的，第一个 for 就填充候选答案向量的第 1 个位置 (下标是 0)，第二个 for 循环填充第 2 个位置，第三个 for 循环填充第 3 个位置。那么如果写 100 个 for 循环，原理也是一样，不过就是填充第 100(候选答案向量的下标是 99) 个位置而已。
现在我们逆向思维来考虑(主动和被动)！之前考虑的是写 for 循环来填充候选答案向量，现在换个想法，我们的候选答案向量要被填充。当候选答案向量的每一维都被填充好，那么就产生了一个候选答案。怎样用代码来描述这样一个过程呢？递归！虽然很难想到，但是使用递归确实可以描述这个过程。在递归的过程中，使用一个变量 k 表示当前正在填充的候选答案向量的下标(0 到 n -1，n 是排列长度)。那么当 k 等于 n 的时候，也就代表当前正在填充的是候选答案向量的下标是 n，而 n 已经超出了该向量，那么也就意味着填充结束！
java 代码：
public class Main {
public static void main(String[] args) throws Exception{
// 等待求解的全排列集合
char[]num = new char[]{‘A’,’B’,’C’};
dfs(num,0,num.length,new char[num.length]);
}
static void dfs(char[]num,int k,int n,char[]temp)
{
if(k == n)
{
if(is_Legal(temp))
System.out.println(temp);
return;
}
for(int i = 0;i < num.length;i++) {
temp[k] = num[i];
dfs(num, k + 1, n, temp);
}
}
static boolean is_Legal(char[]temp)
{
for(int i = 0;i < temp.length;i++)
for(int j = i+1;j < temp.length;j++)
if(temp[i] == temp[j])
return false;
return true;
}
}
细心的读者可能注意到了，递归函数的名字是 dfs。这是什么意思呢？这是深度优先搜索！搜索？遍历？傻傻分不清。
它真的是深度优先搜索吗？是真的吗？是真的！如果是的话，那它的搜索空间 (解空间) 是什么？是向量 [x,y,z] 组成的集合，而 x,y,z in {‘A’,’B’,’C’}。in 代表前面的变量是后面 {} 里的某个元素。这是一个基于 3 维解空间的深度优先搜索！
至此，第一个问题已经解决！接下来我们来看第二个问题！Exciting！
是否有必要产生所有候选答案？当然没有！只要我们在产生候选答案向量的时候，每一次填充完都判断这次填充是否合法，如果不合法则不再继续填充。(不过第一次填充不需要判断，想想为什么？)
java 代码：
public class Main {
public static void main(String[] args) throws Exception{
// 等待求解的全排列集合
char[]num = new char[]{‘A’,’B’,’C’};
dfs(num,0,num.length,new char[num.length]);
}
static void dfs(char[]num,int k,int n,char[]temp)
{
if(k == n)
{
System.out.println(temp);
return;
}
for(int i = 0;i < num.length;i++) {
// 每次填充完就判断，如果不合法，则根本不会向下进行!
temp[k] = num[i];
if(is_Legal(temp,k+1))
dfs(num, k + 1, n, temp);
}
}
//cur 代表这是第几次填充，第 cur 次填充对应着填充
// 第 cur- 1 下标的地方，因此上面调用时为下标 +1, 也就是 k +1
static boolean is_Legal(char[]temp,int cur)
{
for(int i = 0;i < cur;i++)
for(int j = i+1;j < cur;j++)
if(temp[i] == temp[j])
return false;
return true;
}
}
也可以在最前面那种三个 for 循环里每一次都判断，比较简单，读者可以自行尝试。
不知道读者是否听说过剪枝这个词但却一直无法理解它的含义。可以明确是，上面的这个判断就是所谓的剪枝！为什么理解不了剪枝？因为从代码和算法里只能看到剪，而看不到枝。既然是剪枝，那么必须要又枝给你剪才行啊！！！那么这枝在哪呢？看一下我画的图，最左边是候选答案下标。然后右边表明了每一层填充的是哪些字母。这个填充过程像是一颗三叉树，但是这个树实际上不存在的，这只是逻辑上的树而已，而这个逻辑上的树 (或图) 上的路径我们把它称之为枝，剪枝的意思就是把这棵逻辑上的树 (或图) 的某条路径剪去。那么对于这个问题，当填充完第 1 层的时候，哪些路径被剪去了呢？答案是 AA，BB,CC。不过这个图我画的并不完整，因为缺少了第 3 层(只有 0，1，2 层)，第三层是最终的答案，读者可以自行尝试画出。
至此第二个问题也已经解决！读者的内心是不是“这和回溯有毛线关系啊？”别着急，接着看。Interesting！不知道读者有没有觉得，上面的写法很丑陋？我们剪枝与否为什么填充完结果才能判断？难道就不能一开始就知道哪个字母能填哪个不能填吗？就像是站在上帝的视角上看这个问题，好像通灵万物，未卜先知，洞悉一切一样。这个能确实做到，不过不能未卜先知，但是可以利用之前的结果来先知！
我们在递归程序中添加一个 boolean 类型的数组(或 hash 表)，来记录哪个字母现在已经在候选答案向量中了，这样一来，凡是不在的我都可以添加进去，而已经在候选答案向量中的不可添加。
当然也可以不使用一个额外的表去存储哪些字母已经在答案向量中，而是直接在答案向量中查找，因为答案向量已经记录了哪些字母在，哪些字母不在了，只不过这样的话查询的时间消耗比用 Hash 表大！不过原理一样，读者可以自行尝试！
需要注意的是，添加一个字母到候选答案向量中的时候，就要把该字母加入表中，而当这个字母不在答案向量中时需要及时移除。
java 代码：
public class Main {
public static void main(String[] args) throws Exception{
// 等待求解的全排列集合
char[]num = new char[]{‘A’,’B’,’C’};
backtrack(num,0,num.length,new char[num.length],new boolean[num.length]);
}
static void backtrack(char[]num,int k,int n,char[]temp,boolean[]hash)
{
if(k == n)
{
System.out.println(temp);
return;
}
for (int i = 0;i < num.length;i++)
// 如果不在候选答案向量中则添加该字母
if(!hash[i] )
{
hash[i] = true;
temp[k] = num[i];
backtrack(num,k+1,n,temp,hash);
// 下一个 for 循环的时候就是放该层的
// 下一个可以放的字母，这轮循环放的是这个字母
// 那么下一轮循环显然放的不是这个字母了，那么这个字母需要被
// 移除出 hash 表
hash[i] = false;
}
}
}
函数名是 backtrack，意义是回溯！从各个角度看，这里的回溯和刚才的方法唯一不同的就是名字好听，比较高大上，代码简短优美。有人可能会说上面的那种做法是后剪枝，回溯是先剪枝。不过其实两者是一回事，先剪晚剪都是剪。因此！！！回溯其实就是剪了枝的深度优先搜索！！！
说到底，回溯就是个深度优先搜索算法，即便是剪了枝的，也掩盖不了它是个暴力解法。
既然：深度优先搜索 + 剪枝 = 回溯。那么：宽度优先搜索 + 剪枝 =？？？这个我之后有时间再写。
搜索很暴力，很无脑，很低效，可是有一种称之为记忆化的方法，却能够明显改善它的性能。甚至可以使得搜索的效率比强大的动态规划都要好！这就像是小孩子一样，没受教育之前很顽劣，受过教育之后就好像变了一个人一样。有关记忆化搜索，我也有时间再写！
为什么要从暴力法开始讲起？因为暴力是机器唯一听得懂的语言。
