递归（四）—— 初识暴力递归之“打印字符串的全排列”

题目1：序列打印一个字符串的全排列

题目分析：结合一实例来理解题目，str = “abc”的全排列就是所求得的序列是 strp[0~2]的所有位的排列组合，strNew = {“abc”, “acb”, “bac”, “bca”,”cba”,”cab”}

思路1：枚举所有可能性, 假设str = “abcd”

Str[0]	Str[1]	Str[2]	Str[3]
a	b	c	d
	b	d	c
	c	b	d
	c	d	b
	d	c	b
	d	b	c
b	a	c	d
	a	d	c
	c	a	d
	c	d	a
	d	a	c
	d	c	a
c	a	b	d
	a	d	b
	b	a	d
	b	d	a
	d	a	b
	d	b	a
c	a	b	d
	a	d	b
	b	a	d
	b	d	a
	d	a	b
	d	b	a

从表格中可以看到，str[0] 有四种选择，{“a”,”b”, “c” , “d”};

当str[0]的选择确定后，str[1]的选择有3中，即在str[0]确定后，在剩下的三个字符中任意选择一个。

当str[0~1] 确定后，str[2]的选择有两个，即在str[0] 和str[1]选择后剩下的2个字符中，任意选择1个。

当str[0~2] 都确定后，只剩下1个字符，str[3] 只有唯一的字符可用。当没有任何字符可用于继续选择的时候，则认为得到了一个全排列组合。

代码实现

//代码段1
#include <list>
#include <string>
#include <iostream>//rest: 被选择后，剩余的字符；
//path;已经确定的字符所构成的字符串
//ans:存放每一次得到的字符串
void fun_1(vector<char> rest, string path, list<string>& ans) {if (rest.empty()) {ans.push_back(path);}else {int count = rest.size();for (int i = 0; i < count; i++) {char cur = rest[i];rest.erase(rest.begin() + i);fun_1(rest, path+cur, ans);rest.insert(rest.begin()+i, cur);}	}return;
}#define PERMUTATION //全排列int main() {
#ifdef PERMUTATIONlist<string> ans;string strInput = "abc";auto permutationFun= [](string str, list<string>& ans) {if (str.length() == 0) return;const char* arrChar = str.c_str();vector<char> rest(str.size());for (int i = 0; i < str.size(); i++) {rest[i] = arrChar[i];}string path = "";fun_1(rest, path, ans);};permutationFun(strInput, ans);pirnt_list(ans);
#endifreturn 0;
}

代码分析：

当代码运行到第18行的时候，遇到了函数调用，再次进入fun_1,直到 rest.empty() == true, 表示没有剩余字符，所有字符都被使用，则将path存入ans。

当代执行到19行时，表示需要恢复现场。试想，我们每次为当前位选中一个字符后，则认为下一位不可以再使用这个字符，就需要将此字符中rest中删除，而当一个全排类完成后，需要将删除的字符重新加入到rest。

运行结果：

当 strInput = “abcd”；

思路2：

任意一位与其他位进行交换,即可以得到一个新的全排列的组合，直到枚举所有的交换可能。

index_ 0 与其它位交换的可选性是三种，即 index_0 <-> index_0, index_0 <-> index_1, index_0 <-> index_2;

index_1 与其它位交换的选择性只有两种，即index_1 <->index_1 和index_1 <-> index_2;

Index_2 是最后一位，所以它与其它位交换的可能性只有一种 index_2 <-> index_2

当每一次的交换路径从头走到尾，即index_0 到index_n 都完成了交换，我们认为得到了一个全排列序列。接下来回到最近一次做不同决策的位置。例如上例，当执行：

index_0 <->index_0 ==> index_1 <-> index_1 ==> index_2 <-> index_2 之后，最近一次决策就是index_2 <-> index_2, 因为它已经是最后一位，只有这一种决策，那么再回到这个决策的上一个决策，index_1 <-> index_1,这个决策是有不同分支的，index_1 <-> index_2 , 按照这条新路径继续走下去，直到最后一位。然后回到index_0 <-> index_0。

index_0 是有其它决策的，index_0 <-> index_1 ,然后按照这条路径继续交换下去，逻辑同上。

直达index_0 的所有决策分支都走完，则认为找到了所有的全排列序列。

代码实现

//代码段2
#include <list>
#include <string>
#include <iostream>void swap(string& str, int i, int j) {char temp = str[i];str[i] = str[j];str[j] = temp;
}void pirnt_list(list<string> listInput) {for (list<string>::iterator item = listInput.begin(); item != listInput.end(); item++) {std::cout << *item << std::endl;}
}//strPre: 每一次全排列后得到的字符串
//index: 当前需要确定的字符串位
//ans:存放每一次全排列得到的字符串
void fun_2(string strPre, int index, list<string>& ans) {if (index == strPre.length()) {ans.push_back(strPre);}else {for (int i = index; i < strPre.length(); i++) {swap(strPre, index, i);fun_2(strPre, index + 1, ans);swap(strPre, index, i);}}return;
}
#define PERMUTATION //全排列
int main() {  
#ifdef PERMUTATIONlist<string> ans;string strInput = "abcd";auto permutationFun = [](string str, list<string>& ans) {if (str.length() == 0) return;const char* arrChar = str.c_str();vector<char> rest(str.size());for (int i = 0; i < str.size(); i++) {rest[i] = arrChar[i];}string path = "";fun_2(str, 0, ans);};permutationFun(strInput, ans);pirnt_list(ans);
#endifreturn 0;
}

代码分析：

递归的base case 就是第22行 if(index == strPre.length()), 即当字符串中的所有index 都完成了交换，则将当前得到的序列存入ans
每一次将新的全排列序列写入ans后（即执行下一个支路前），都要恢复现场，即第29行代码.

运行结果：

问题补充：打印一个字符串的全部排列，要求不出现重复排列。

问题分析：解决问题的思路与思路2是一样的，只是在进行两个数据位交换的时候，增加一个判断，判断当前数据位与要进行交换的数据位的字符是否相同，如果相同，则取消交换。

例如str = “aac”

index_0 与index_1 的字符相同，都是“a”，所以index_0 <-> index_1交换的这条支路的结果与 index _0 <->index_0 这条支路的结果式样的。所以，当判断到index_i <-> index_j 两个交换位的字符相同，则会推出交换。

代码实现

//代码段3
#include <list>
#include <string>
#include <iostream>void swap(string& str, int i, int j) {char temp = str[i];str[i] = str[j];str[j] = temp;
}void pirnt_list(list<string> listInput) {for (list<string>::iterator item = listInput.begin(); item != listInput.end(); item++) {std::cout << *item << std::endl;}
}void fun_3(string strPre, int index, list<string>& ans) {if (index == strPre.length()) {ans.push_back(strPre);}else {bool* visited = new bool[256];for (int i = 0; i < 256; i++) visited[i] = false;for (int i = index; i < strPre.length(); i++) {if (!visited[strPre[i]]) {visited[strPre[i]] = true;swap(strPre, index, i);fun_3(strPre, index + 1, ans);swap(strPre, index, i);}}delete[] visited;}return;
}#define PERMUTATION //全排列
int main() {  
#ifdef PERMUTATIONlist<string> ans;string strInput = "aac";auto permutationFun = [](string str, list<string>& ans) {if (str.length() == 0) return;const char* arrChar = str.c_str();vector<char> rest(str.size());for (int i = 0; i < str.size(); i++) {rest[i] = arrChar[i];}string path = "";fun_3(str, 0, ans);};permutationFun(strInput, ans);pirnt_list(ans);
#endifreturn 0;
}

代码分析：

设置标志位数据结构 bool* visited = new bool[256]; 初始化为false， visited[i] 表示对应assicll码为i

的字符是否出现过。

for (int i = index; i < strPre.length(); i++) {
if (!visited[strPre[i]]) {
....
}

}

i 位置上的字符与index上字符要交换，只有i 位置上的字符是不曾出现过的，才会交换，如果visiited[strpre[i]] == ture, 表示在这条路基上这个字符与index发生过交换，只要交换过这个字符，就被置为true。

运行结果：

str = "aac", 使用fun_2 没有去重处理：