题目描述:
输入一个字符串,打印出该字符串中字符的所有排列。
基本思路:
从字符串中选出一个字符作为排列的第一个字符,然后对剩余的字符进行全排列,如此递归,从而得到所有字符的全排列。以对字符”abc”进行全排列为例,可以按下述步骤执行:
将a固定在第一位,求后面bc的排列
将b固定在第一位,求后面ac的排列
将c固定在第一位,求后面ab的排列
#include #include #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]); 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 #include #include using namespace std; #include 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
阅读(650) | 评论(0) | 转发(0) |