【本文鏈接】
http://www.cnblogs.com/hellogiser/p/string-combination.html
【題目】
題目：輸入一個字符串，輸出該字符串中字符的所有組合。舉個例子，如果輸入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 : Defines the entry point for the console application.
//
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/5/24
*/
#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;
// print string combination
void Print(vector<char> &result)
{
vector<char>::const_iterator iterBegin = result.begin();
vector<char>::const_iterator iterEnd = result.end();
for (; iterBegin != iterEnd; ++ iterBegin)
printf("%c", *iterBegin);
printf("\n");
}
// get string combination recursively
// choose m chars from str
void Combination(char *str, unsigned int m, vector<char> &result)
{
if(NULL == str || (*str == '\0' && m > 0))
return;
// base cases
if (m == 0)
{
// we have got a combination,print it
Print(result);
return;
}
// (1)choose current char
result.push_back(*str);
// choose m-1 chars from remaining n-1 chars
Combination(str + 1, m - 1, result);
// (2) not choose current char
result.pop_back();
// choose m chars from remaining n-1 chars
Combination(str + 1, m, result);
}
// string combination
void StringCombination(char *str)
{
if(NULL == str || *str == '\0')
return;
int len = strlen(str);
vector<char> result;
for (int i = 1; i <= len; ++i)
Combination(str, i, result);
}
void test_base(char *str)
{
StringCombination(str);
printf("---------------------\n");
}
void test_case1()
{
char str[] = "";
test_base(str);
}
void test_case2()
{
char str[] = "a";
test_base(str);
}
void test_case3()
{
char str[] = "abc";
test_base(str);
}
void test_main()
{
test_case1();
test_case2();
test_case3();
}
int _tmain(int argc, _TCHAR *argv[])
{
test_main();
return 0;
}
/*
---------------------
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
*/
void StringCombinationUsingBitwise(char *str)
{
// use bitwise operations to get string combination
if(NULL == str || *str == '\0')
return;
int len = strlen(str);
if (len >= 32)
return;
int sum = 1 << len;
for (int i = 1; i < sum; ++i)
{
for (int j = 0; j < len; j++)
{
if ((i >> j) & 0x1)
{
// choose char at str[j]
printf("%c", str[j]);
}
}
printf("\n");
}
}
相對於 【遞歸法求組合】，【位運算求組合】速度更快，其時間復雜度為T=n*2n，但是n不能超過32.
【參考】
http://zhedahht.blog.163.com/blog/static/2541117420114172812217/
http://zhuyanfeng.com/archives/3246
http://blog.csdn.net/hackbuteer1/article/details/7462447
http://blog.csdn.net/wuzhekai1985/article/details/6643127
【本文鏈接】
http://www.cnblogs.com/hellogiser/p/string-combination.html
