1 问题
求字符串的全排列，比如字符串abc，它的全排列如下
abc, acb, bac, bca, cad, cba
2 思路
我们先固定第一个字符，这里的第一个字符肯定是这个字符串里面字符串的全子集（不包含重复），abc字符串，我们a和a交换，这里也就是固定a字符的，然后我们只需要求出后面bc字符的全排列，这个时候我们可以用递归，我们依然b和b进行交换，c和c进行交换，到了末尾我们递归就结束，记得return.我们可以得出bc全排列的一种既bc,然后我们b和c需要交换位置，变成了cb,然后我们b和b进行了一次交换，然后我们可以得到bc全排列的一种既cb,所以固定a字符，我们可以得到全排列字符串abc acb,所以依次类推，我们可以固定b字符和c字符求出所以字符串的全排列
3 代码实现
c++版本
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; class Permutation{ private: void permutation(string str, int begin); public: vector<string> permutation(string str); vector<string> result; }; vector<string> Permutation::permutation(string str) { if (str.length() == 0) { return result; } permutation(str, 0); sort(result.begin(), result.end()); return result; } void Permutation::permutation(string str, int begin) { if (begin == str.length()) { result.push_back(str); return; } for (int i = begin; i < str.length(); ++i) { if (i != begin && str[i] == str[begin]) continue; //这里开始交换第一个元素和后面的元素，也就是起到固定的作用 swap(str[begin], str[i]); //递归后面的子字符串 permutation(str, begin + 1); //交换了要记得还原 swap(str[i], str[begin]); } } int main() { Permutation h; h.permutation("abc"); vector<string> result = h.result; for(int i = 0; i < result.size(); ++i) { std::cout << result[i] << std::endl; } return 0; }
c版本
#include <stdio.h> void permutation(char *str); void permutation_core(char *str, char *begin); void permutation(char *str) { if (str == NULL) { printf("str is NULL\n"); return; } permutation_core(str, str); } void permutation_core(char *str, char *begin) { if (*begin == '\0') { printf("%s\n", str); } else { for (char *ch = begin; *ch != '\0'; ++ch) { char temp = *ch; *ch = *begin; *begin = temp; permutation_core(str, begin + 1); temp = *ch; *ch = *begin; *begin = temp; } } } int main() { //这里不能用char *str = "adc",因为我们需要交换字符串里面的字符，需要操作栈内存 char str[] = "abc"; permutation(str); return 0; }
这样写，如果有重复的字符就有问题，比如ada,我们优化如下，去掉重
#include <stdio.h> #include <string.h> void permutation(char *str); void swap(char *str, int start, int end); void permutation_core(char *str, int begin, int end); void permutation(char *str) { if (str == NULL) { printf("str is NULL\n"); return; } int len = strlen(str); printf("len is %d\n", len); permutation_core(str, 0, len); } void permutation_core(char *str, int begin, int end) { if (begin == end) { printf("%s\n", str); } else { for (int i = begin; i < end; ++i) { if (i != begin && str[i] == str[begin]) continue; swap(str, i, begin); permutation_core(str, begin + 1, end); swap(str, i, begin); } } } void swap(char str[], int start, int end) { char ch = str[start]; str[start] = str[end]; str[end] = ch; } int main() { //这里不能用char *str = "adc",因为我们需要交换字符串里面的字符，需要操作栈内存 char str[] = "abc"; permutation(str); return 0; }
4 运行结果
c++版本运行结果
abc acb bac bca cab cba
c版本运行结果
abc acb bac bca cba cab
