字符串的全组合
题目描述：
输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。
分析和解法：
解法一：递归求解
可以考虑求长度为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。
源代码如下：
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
//从一个字符串中选 m 个元素
void Combination_m(char* str, int m, vector<char> &result)
{
//字符串为空，或者长度达不到 m
if (str == NULL || (*str == '\0' && m != 0))
return;
//出口，输出组合
if(m == 0)
{
static int count = 0;
cout << ++count << ":";
for (int i = 0; i < result.size(); i++)
cout << result[i];
cout << endl;
return;
}
result.push_back(*str);
Combination_m(str+1, m-1, result);
result.pop_back();
Combination_m(str+1, m, result);
}
//求一个字符串的组合
void Combination(char* str)
{
if (str == NULL || *str == '\0')
return;
int num = strlen(str);
for (int i = 1; i <= num; i++)
{
vector<char> result;
Combination_m(str, i, result);
}
}
int main()
{
char str[20];
cin >> str;
Combination(str);
return 0;
}
分析：如果输入中有重复字符，上面的程序并不可以去掉重复的组合。一种处理方法是在事前进行一次遍历，剔除重复字符，记录所有不同字符的集合，再传入Combination()函数中；还有一种方法是在Combination_m()函数中加入判断，判断当前组合是否已经存在（即打印）。
解法二：位运算
用相应位数的二进制数来表示一种组合，用 “1” 来表示取该字符，用 “0” 来表示不取该字符，依据二进制数来输出相应组合。
源代码如下：
#include <iostream>
#include <cstring>
using namespace std;
void print_subset(char* str, int n, int s)
{
static int count = 0;
cout << ++count << ":";
for (int i = 0; i < n; i++)
{
if (s & (1 << i)) //判断s的二进制中哪些位为 1，就取哪些位
cout << str[i];
}
cout << endl;
}
void subset(char* str, int n)
{
for (int i = 1; i < (1 << n); i++)
print_subset(str, n, i);
}
int main()
{
char str[20];
cin >> str;
subset(str, strlen(str));
return 0;
}
分析：这种解法十分巧妙，借助于二进制数来表示组合，而且可以十分方便快速的知道有多少种组合，即(1 << n) - 1。但是上面的代码也不能去除重复的组合。这种解法就只能在事前先筛选出无重复的字符在进行判断输出。
特别注意：
在这里我写一下只有大写字母的字符时的筛选函数：
char s_str[26];
void Select(char* str, int n)
{
int j = 0;
int hash = 0; //我们用其中的26位来表示是否含有字符
for (int i = 0; i < n; ++i)
{
int temp = hash;
hash |= (1 << (str[i] - 'A')); //把1左移若干位，1是标志位，表示有该字符
if (temp != hash)
s_str[j++] = str[i];
}
}
参考资料：《编程之法》The Art of Programming By July
字符串的全排列和组合算法
网友评论