C语言字母的组合,C语言求字母的全部组合
使用的递归的方法：既然是组合，则顺序不要求顺序了。
主要原理就是从第一个字符开始，分两种情况：1.留下此字符；2.去除此字符。 再对剩下的字符求组合。
然后再第二个字符，分两种情况，再对剩下的字符求组合
#include
#include
#include
template
inline void swap(T &a , T &b)
{
T tmp;
tmp = a;
a = b;
b = tmp;
}
void doPrintAllCombination(char *str , int begin , int end)
{
if(begin == end) {
char tmp;
if(end != 0) { //i要此字符时
tmp = str[end];
str[end] = ;
printf("%s ",str);
str[end] = tmp;
}
tmp = str[end+1]; //不要此字符
str[end+1] = ;
printf("%s " , str);
str[end+1] = tmp;
return;
}
//第二种情况，去除此字符
swap(str[begin],str[end]);
doPrintAllCombination(str , begin , end-1);
swap(str[begin] , str[end]);
//第一种情况，留下此字符
doPrintAllCombination(str , begin+1 , end);
}
void printAllCombination(char *str)
{
doPrintAllCombination(str , 0 , strlen(str)-1);
}
int main(int argc , char *argv[])
{
if(argc != 2) {
printf("usage: %s " , argv[0]);
return -1;
}
char *str = (char*)malloc(strlen(argv[1]) + 1);
strcpy(str , argv[1]);
printf("orignate string : %s " , str);
printAllCombination(str);
free(str);
return 0;
}
结果：
orignate string : abc
b
c
cb
a
ac
ab
abc
结果中有些字符的顺序改变了，如cb ,,按正常顺序可能是bc,,,
这是因为我的这个程序的空间复杂度为O(1)
如果你要求产生的组合与原始字符的顺序一致，，则可以使用mask代替，，标记使用不使用此字符。此时空间复杂度为O(N)
反正时间复杂度都为O(N)
使用的递归的方法：既然是组合，则顺序不要求顺序了。 主要原理就是从第一个字符开始，分两种情况：1.留下此字符；2.去除此字符。 再对剩下的字符求组合。 然后再第二个字符，分两种情况，再对剩下的字符求组合 #include #include #include template inline void swap(T &a , T &b) { T tmp; tmp = a; a = b; b = tmp; } void doPrintAllCombination(char *str , int begin , int end) { if(begin == end) { char tmp; if(end != 0) { //i要此字符时 tmp = str[end]; str[end] = ; printf("%s ",str); str[end] = tmp; } tmp = str[end+1]; //不要此字符 str[end+1] = ; printf("%s " , str); str[end+1] = tmp; return; } //第二种情况，去除此字符 swap(str[begin],str[end]); doPrintAllCombination(str , begin , end-1); swap(str[begin] , str[end]); //第一种情况，留下此字符 doPrintAllCombination(str , begin+1 , end); } void printAllCombination(char *str) { doPrintAllCombination(str , 0 , strlen(str)-1); } int main(int argc , char *argv[]) { if(argc != 2) { printf("usage: %s " , argv[0]); return -1; } char *str = (char*)malloc(strlen(argv[1]) + 1); strcpy(str , argv[1]); printf("orignate string : %s " , str); printAllCombination(str); free(str); return 0; } 结果： orignate string : abc b c cb a ac ab abc 结果中有些字符的顺序改变了，如cb ,,按正常顺序可能是bc,,, 这是因为我的这个程序的空间复杂度为O(1) 如果你要求产生的组合与原始字符的顺序一致，，则可以使用mask代替，，标记使用不使用此字符。此时空间复杂度为O(N) 反正时间复杂度都为O(N)