给定一个字符串，输出其所有的可能排列
转载请注明来自souldak，微博:@evagle
Question：
给你一个字符串例如abb输出它包含的字符的所有可能排列。
例如abb输出3个：abb,bab,bba
Answer：
假设我们自己来做，那做法如下：
1. 有n个字符相当于n个格子。
2. 先放第一个格子，从n个字符中任选一个，放到这个格子即可，放完就剩下n-1个格子和n-1个字符
3. 放第二个格子，从n-1个字符中任选一个
。。。
n. 最后一个格子，只剩下一个字符，不用选，输出放好的结果
第二步到第n步其实问题本质是一样的，k个字符选一个，放到格子里即可。problem与subproblem的关系，所以我们可以用递归求解。
1. 获得字符串s，得到长度n
2. 轮询确定s[0]放哪个字符，共有n个，如果放第k个，就把s[k]放到s[0],s[0]放到s[k]
3. 放好后就求解子问题，即求s[1]~s[n-1]的排列
4. 如果已经求解到s[n-1],输出结果
Attention：传入的str应该是char数组，不能是这样定义的：char* str = "abc"; 具体为什么请参看：//rm_dup: true for remove duplicated stringsvoid permutation(char* str, int start, bool rm_dup){ if(str==NULL||str=="") return; if(start==strlen(str)-1) cout<<str<<endl; bool visit[256]; memset(visit,0,sizeof(visit)); for(int i=start;i<strlen(str);i++){ if(!visit[str[i]]||!rm_dup){ visit[str[i]] = true; std::swap(str[start],str[i]); permutation(str,start+1,rm_dup); std::swap(str[start],str[i]); } } }
