大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > 2种方法求字符串的组合

2种方法求字符串的组合

关键词:字符串C++  阅读(1094) 赞(14)

[摘要]本文是对2种方法求字符串的组合的讲解,对学习C++编程技术有所帮助,与大家分享。

题目:输入一个字符串,输出该字符串中字符的所有组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc。

【分析】

在之前的博文28.字符串的排列[StringPermutation]中讨论了如何用递归的思路求字符串的排列。同样,本题也可以用递归的思路来求字符串的组合。


【递归法求组合】

可以考虑求长度为n的字符串中m个字符的组合,设为C(n,m)。原问题的解即为C(n, 1), C(n, 2),...C(n, n)的总和。对于求C(n, m),从第一个字符开始扫描,每个字符有两种情况,要么被选中,要么不被选中。如果被选中,递归求解C(n-1, m-1);如果未被选中,递归求解C(n-1, m)。不管哪种方式,n的值都会减少,递归的终止条件n=0或m=0。

【代码】

C++ Code
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//55_StringCombination.cpp:Definestheentrypointfortheconsoleapplication.
//
/*
version:1.0
author:hellogiser
blog:http://www.cnblogs.com/hellogiser
date:2014/5/24
*/

#include"stdafx.h"
#include<vector>
#include<iostream>
usingnamespacestd;

//printstringcombination
voidPrint(vector<char>&result)
{
vector<char>::const_iteratoriterBegin=result.begin();
vector<char>::const_iteratoriterEnd=result.end();

for(;iterBegin!=iterEnd;++iterBegin)
printf("%c",*iterBegin);
printf("\n");
}

//getstringcombinationrecursively
//choosemcharsfromstr
voidCombination(char*str,unsignedintm,vector<char>&result)
{
if(NULL==str||(*str=='\0'&&m>0))
return;

//basecases
if(m==0)
{
//wehavegotacombination,printit
Print(result);
return;
}
//(1)choosecurrentchar
result.push_back(*str);
//choosem-1charsfromremainingn-1chars
Combination(str+1,m-1,result);

//(2)notchoosecurrentchar
result.pop_back();
//choosemcharsfromremainingn-1chars
Combination(str+1,m,result);
}

//stringcombination
voidStringCombination(char*str)
{
if(NULL==str||*str=='\0')
return;
intlen=strlen(str);
vector<char>result;
for(inti=1;i<=len;++i)
Combination(str,i,result);
}

voidtest_base(char*str)
{
StringCombination(str);
printf("---------------------\n");
}

voidtest_case1()
{
charstr[]="";
test_base(str);
}

voidtest_case2()
{
charstr[]="a";
test_base(str);
}

voidtest_case3()
{
charstr[]="abc";
test_base(str);
}

voidtest_main()
{
test_case1();
test_case2();
test_case3();
}

int_tmain(intargc,_TCHAR*argv[])
{
test_main();
return0;
}
/*
---------------------
a
---------------------
a
b
c
ab
ac
bc
abc
---------------------
*/

由于组合可以是1个字符的组合,2个字符的组合……一直到n个字符的组合,因此在函数void StringCombination(char *str)中,需要一个for循环。另外,用一个vector来存放选择放进组合里的字符。


【位运算求组合】

另外本题还有一个巧妙的思路,可以从位运算出发求组合。用一个二进制数字,来决定字符的取舍,某一位为1,则取对应的字符,若为0则不取,就能够实现字符组合。

例如对于“abc”,长度为3,则共有7种组合可能。让num 从1自增到7,跟字符的每一位进行判断,是否取舍。

比如:num=1,即001时:

(1)j指向第1个字符,(a>>j)&1==1,则取a;

(2)j指向第2个字符,(a>>j)&1==0,则舍弃b;

(3)j指向第3个字符,(a>>j)&1==0,则舍弃c;

此次组合的字符串为a;

以此类推。

当num=7,即111时:

(1)j指向第1个字符,(a>>j)&1==1,则取a;

(2)j指向第2个字符,(a>>j)&1==1,则取b;

(3)j指向第3个字符,(a>>j)&1==1,则取c;

此次组合的字符串为abc;

那么当num依次取完所有的值,就可以得到所有的字符串组合。

【代码】

C++ Code
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
/*
version:1.0
author:hellogiser
blog:http://www.cnblogs.com/hellogiser
date:2014/5/24
*/
voidStringCombinationUsingBitwise(char*str)
{
//usebitwiseoperationstogetstringcombination
if(NULL==str||*str=='\0')
return;
intlen=strlen(str);
if(len>=32)
return;
intsum=1<<len;
for(inti=1;i<sum;++i)
{
for(intj=0;j<len;j++)
{
if((i>>j)&0x1)
{
//choosecharatstr[j]
printf("%c",str[j]);
}
}
printf("\n");
}
}

相对于【递归法求组合】,【位运算求组合】速度更快,其时间复杂度为T=n*2n,但是n不能超过32.

【注意】

多谢“路上的脚印”的提醒,该算法只能适用于字符串中字符都不相同的情形。如果有相同字符,则不再适合,需要进一步修正。



相关评论