如何求ABC的全排列？--如何理解回溯算法？
风和日丽 2019-07-01
什么是全排列？
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
那么ABC的全排列有哪些？根据定义得到：
ABC
ACB
BAC
BCA
CAB
CBA
如何通过程序求解？
方法一：
暴力法，为什么是暴力法？因为暴力是机器唯一听得懂的语言。
如何暴力？
对一个空的字符串添加字母，添加三次，这个字母是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，意义是回溯！
从各个角度看，这里的回溯和刚才的方法唯一不同的就是名字好听，比较高大上，代码简短优美。
有人可能会说上面的那种做法是后剪枝，回溯是先剪枝。不过其实两者是一回事，先剪晚剪都是
剪。
因此！！！
回溯其实就是剪了枝的深度优先搜索！！！
说到底，回溯就是个深度优先搜索算法，即便是剪了枝的，也掩盖不了它是个暴力解法。
既然：深度优先搜索+剪枝=回溯。
那么：宽度优先搜索+剪枝=？？？
这个我之后有时间再写。
搜索很暴力，很无脑，很低效，可是有一种称之为记忆化的方法，却能够明显改善它的性能。
甚至可以使得搜索的效率比强大的动态规划都要好！
这就像是小孩子一样，没受教育之前很顽劣，受过教育之后就好像变了一个人一样。
有关记忆化搜索，我也有时间再写！
为什么要从暴力法开始讲起？因为暴力是机器唯一听得懂的语言。
