字符串的排列与组合

- 日理万妓 2022-05-21 09:18 235阅读 0赞

**字符串的全排列**  
题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。  
分析：对于这个问题可以把字符串分成两个部分，一部分是字符串的第一个字符，另一部分是剩余部分。即就是两个步骤，1：求后面n-1个字符的全排列；2、把第一个字符与后面字符分别交换。而求后面n-1个字符的排列也可采用该方法，所以可以递归实现为：

vector<string> permutation(string s)
    {
        vector<string> str;
        if(s.size()==0)
            return str;
        permutation(s,0,str);
        return str;
    }
    
    void permutation(string s, int pbegin,vector<string>&str)
    {
        if(pbegin==s.size())
        {
            str.push_back(s);
            cout<<s<<endl;
        }
        else
        {
            for(int i=pbegin;i<s.size();++i)
            {
                if(i!=pbegin && s[i]==s[pbegin])
                    continue;
                swap(s[i],s[pbegin]);
                permutation(s,pbegin+1,str);
                swap(s[i],s[pbegin]);
            }
        }
    }
    /*另一种一样的方法
    void permutation(char* str,char* pbegin)
     {
         if (str==nullptr)
         {
             return;
         }
         if (*pbegin == '\0')
             printf("%s\n ", str);
         else
         {
             for (char* pctr = pbegin; *pctr != '\0'; ++pctr)
             {
                 if (pctr!=pbegin && *pctr == *pbegin)
                     continue;
                 char c = *pctr;
                 *pctr = *pbegin;
                 *pbegin = c;
                 permutation(str, pbegin + 1);
                 c = *pctr;
                 *pctr = *pbegin;
                 *pbegin = c;
             }
         }
     }
     */

**字符串的组合**  
求输入字符的组合，例如：输入三个字符a、b、c则它们的组合有a、b、c、ab、ac、bc、abc。  
分析：对于输入n个字符，则这n个字符能够构成长度为1、2、…、n的组合。在求长度为m的组合的时候，我们把这n个字符分成两个部分：第一个字符和其余所有的字符。如果组合里面包含第一个字符，则就在剩余字符里面选取m-1个字符；如果组合里面不包含第一个字符，则就在剩余字符里面选取m个字符。即可分解成两个子问题求n-1中m-1的组合和求n-1中的m组合。实现如下：

vector<string> Combination(string s)
    {
        vector<string> result;
        vector<string> str;
        if(s.size()==0)
            return result;
        for(int num=1;num<s.size();++num)
        {
            Combination(s,0,num,str,result);
        }
        return result;
    }
    void Combination(string s,int pbegin,int num,vector<char>&str,vector<string> &result)
    {
        if(num==0)
        {
            string s;
            for(int i=0;i<str.size();++i)
                s+=str[i];
            result.push_back(s);
            cout<<s<<endl;
            return;
        }
        if(pbegin<s.size())
        {
            Combination(s,pbegin+1,num,str,result);
            str.push_back(s[pbegin]);
            Combination(s,pbegin+1,num-1,str,result);
            str.pop_back(s[pbegin]);
        }
    }

NOTE :还可以使用[next\_permutation][next_permutation],是STL中提供的算法，按字典序排列。

字符串全排列拓展问题：  
八皇后问题：在8×8的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。下图中的每个黑色格子表示一个皇后，这就是一种符合条件的摆放方法。请求出总共有多少种摆法。  
分析：由于八个皇后的任意两个不能处在同一行，那么这肯定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex\[8\]，数组中第i个数字表示位于第i行的皇后的列号。先把ColumnIndex的八个数字分别用0-7初始化，接下来我们要做的事情就是对数组ColumnIndex做全排列。由于我们是用不同的数字初始化数组中的数字，因此任意两个皇后肯定不同列。我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上，也就是数组的两个下标i和j，是不是i-j==ColumnIndex\[i\]-Column\[j\]或者j-i==ColumnIndex\[i\]-ColumnIndex\[j\]。

字符串组合问题拓展：  
输入两个整数n和m，从数列1,2,3…n中随意取几个数，使其和等于m，要求列出所有的组合。

void find_factor(int sum, int n,vector<int>&rec, vector<vector<int>>&result)
    {
        //递归出口  
        if (n <= 0 || sum <= 0)
            return;
        //输出找到的数  
        if (sum == n)
        {
            rec.push_back(n);
            for (int i = 0; i<rec.size(); ++i)
                cout << rec[i] << " ";
            rec.pop_back();
            cout << endl;
            result.push_back(rec);
        }
        rec.push_back(n);
        find_factor(sum - n, n - 1,rec,result);//n放在里面  
        rec.pop_back();
        find_factor(sum, n - 1, rec, result);//n不放在里面  
    }
    
    int main(void)
    {
        int sum, n;
        cin >> sum >> n;
        vector<vector<int>> result;
        vector<int> rec;
        cout << "所有可能的序列，如下：" << endl;
        find_factor(sum, n, rec, result);
        return 0;
    }

[next_permutation]: https://blog.csdn.net/c18219227162/article/details/50301513