字符串的全组合

题目描述：

输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入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
字符串的全排列和组合算法