joomla 网站建设教程,西安seo服务外包,html5视频标签,燕郊seo1 问题
求字符串的全排列#xff0c;比如字符串abc#xff0c;它的全排列如下
abc, acb, bac, bca, cad, cba 2 思路
我们先固定第一个字符#xff0c;这里的第一个字符肯定是这个字符串里面字符串的全子集#xff08;不包含重复#xff09;#xff0c;abc字符串…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 algorithmusing namespace std;class Permutation{
private:void permutation(string str, int begin);
public:vectorstring permutation(string str);vectorstring result;
};vectorstring 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);vectorstring result h.result;for(int i 0; i result.size(); i){std::cout result[i] std::endl; }return 0;
}c版本
#include stdio.hvoid 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.hvoid 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
