题目描述： 输入一个字符串，打印出该字符串中字符的所有排列。 基本思路： 从字符串中选出一个字符作为排列的第一个字符，然后对剩余的字符进行全排列，如此递归，从而得到所有字符的全排列。以对字符”abc”进行全排列为例，可以按下述步骤执行： 将a固定在第一位，求后面bc的排列 将b固定在第一位，求后面ac的排列 将c固定在第一位，求后面ab的排列
#include<stdio.h> #include<stdlib.h> #define swap(t,x,y) (t = (x),x = (y),y = (t)) void CalcAllPermutation(char *perm,int from,int to) { if (to < 0) return ; int i = 0; char t; if (from == to) { for (i = 0;i <= to;i++) printf("%c",perm[i]); printf("\n"); } else { for (i = from;i <= to;i++) { swap(t,perm[i],perm[from]);//将from-to中的一个元素固定在第一位 CalcAllPermutation(perm,from+1,to); swap(t,perm[i],perm[from]);//恢复以前的状态 } } } int main() { char s[] = "abcd"; CalcAllPermutation(s,0,3); return 0; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32运行结果(centos5.5) [root@localhost ~]# ./a.out abcd abdc acbd acdb adcb adbc bacd badc bcad bcda bdca bdac cbad cbda cabd cadb cdab cdba dbca dbac dcba dcab dacb dabc 题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。 上面我们详细讨论了如何用递归的思路求字符串的排列。同样，本题也可以用递归的思路来求字符串的组合。 假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：第一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；第二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码：
#include<iostream> #include<vector> #include<cstring> using namespace std; #include<assert.h> void Combination(char *string ,int number,vector<char> &result); void Combination(char *string) { assert(string != NULL); vector<char> result; int i , length = strlen(string); for(i = 1 ; i <= length ; ++i) Combination(string , i ,result); } void Combination(char *string ,int number , vector<char> &result) { assert(string != NULL); if(number == 0) { static int num = 1; printf("第%d个组合\t",num++); vector<char>::iterator iter = result.begin(); for( ; iter != result.end() ; ++iter) printf("%c",*iter); printf("\n"); return ; } if(*string == '\0') return ; result.push_back(*string); Combination(string + 1 , number - 1 , result); result.pop_back(); Combination(string + 1 , number , result); } int main(void) { char str[] = "abc"; Combination(str); return 0; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46运行结果如下：(centos5.5) [root@localhost ~]# ./a.out 第1个组合 a 第2个组合 b 第3个组合 c 第4个组合 ab 第5个组合 ac 第6个组合 bc 第7个组合 abc
<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"16"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];</script> 阅读(138) | 评论(0) | 转发(0) | 0上一篇：字符串的包含
下一篇：经典排序算法之堆排序
相关热门文章 test123编写安全代码——小心有符号数...使用openssl api进行加密解密...一段自己打印自己的c程序...彻底搞定C语言指针详解-完整版... 给主人留下些什么吧！~~ 评论热议