C语言求字母的全部组合

C语言求字母的全部组合

使用的递归的方法：既然是组合，则顺序不要求顺序了。

主要原理就是从第一个字符开始，分两种情况：1.留下此字符；2.去除此字符。 再对剩下的字符求组合。

然后再第二个字符，分两种情况，再对剩下的字符求组合

1. #include <stdlib.h>
2. #include <stdio.h>
3. #include <string.h>
5. template <typename T>
6. inlinevoid swap(T &a , T &b)
7. {
8. T tmp;
9. tmp = a;
10. a = b;
11. b = tmp;
12. }
14. void doPrintAllCombination(char *str , int begin , int end)
15. {
16. if(begin == end) {
17. char tmp;
18. if(end != 0) { //i要此字符时
19. tmp = str[end];
20. str[end] = '\0';
21. printf("%s\n",str);
22. str[end] = tmp;
23. }
25. tmp = str[end+1]; //不要此字符
26. str[end+1] = '\0';
27. printf("%s\n" , str);
28. str[end+1] = tmp;
29. return;
30. }
31. //第二种情况，去除此字符
32. swap(str[begin],str[end]);
33. doPrintAllCombination(str , begin , end-1);
34. swap(str[begin] , str[end]);
35. //第一种情况，留下此字符
36. doPrintAllCombination(str , begin+1 , end);
37. }
38. void printAllCombination(char *str)
39. {
40. doPrintAllCombination(str , 0 , strlen(str)-1);
41. }
43. int main(int argc , char *argv[])
44. {
45. if(argc != 2) {
46. printf("usage: %s <string>\n" , argv[0]);
47. return -1;
48. }
50. char *str = (char*)malloc(strlen(argv[1]) + 1);
51. strcpy(str , argv[1]);
52. printf("orignate string : %s\n" , str);
53. printAllCombination(str);
54. free(str);
55. return 0;
56. }

结果：

orignate string : abc
b
c
cb
a
ac
ab
abc

结果中有些字符的顺序改变了，如cb ,,按正常顺序可能是bc,,,

这是因为我的这个程序的空间复杂度为O(1)

如果你要求产生的组合与原始字符的顺序一致，，则可以使用mask代替，，标记使用不使用此字符。此时空间复杂度为O(N)

反正时间复杂度都为O(N)