首页 > 代码库 > 字符串的排列&组合

字符串的排列&组合

2024-07-04 20:19:12   230人阅读

问题1 ：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

    思路：这是个递归求解的问题。递归算法有四个特性：（1)必须有可达到的终止条件，否则程序将陷入死循环；（2）子问题在规模上比原问题小；（3）子问题可通过再次递归调用求解；（4）子问题的解应能组合成整个问题的解。

    对于字符串的排列问题。如果能生成n - 1个元素的全排列，就能生成n个元素的全排列。对于只有1个元素的集合，可以直接生成全排列。全排列的递归终止条件很明确，只有1个元素时。

#include <iostream>

using namespace std;

void Permutation(char *pStr, char *pBegin);

void Permutation(char *pStr)//提供的公共接口
{
    if (pStr == NULL)
    {
        return;
    }
    Permutation(pStr, pStr);
}

void Permutation(char *pStr, char *pBegin)
{
    if(*pBegin == ‘\0‘)
    {
        cout << pStr << endl;
    }
    else
    {
        for (char *pCh = pBegin; *pCh != ‘\0‘; ++pCh)
        {
            swap(*pCh,*pBegin);//交换
            Permutation(pStr, pBegin + 1);
            swap(*pCh,*pBegin);//恢复还原
        }
    }
}
void swap(char a, char b)
{
    char temp = a;
    a = b;
    b = temp;
}
int main()
{
    char string[100];
    while(cin>>string)
        Permutation(string);
    return 0;
}

 问题是存在重复时无法实现

去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换

#include <iostream>

using namespace std;

void Permutation(char *pStr, char *pBegin);

void Permutation(char *pStr)//提供的公共接口
{
    if (pStr == NULL)
    {
        return;
    }
    Permutation(pStr, pStr);
}
bool IsSwap(char* pBegin , char* pEnd)
{
    char *p;
    for(p = pBegin ; p < pEnd ; p++)
    {
        if(*p == *pEnd)
            return false;
    }
    return true;
}
void Permutation(char *pStr, char *pBegin)
{
    if(*pBegin == ‘\0‘)
    {
        cout << pStr << endl;
    }
    else
    {
        for (char *pCh = pBegin; *pCh != ‘\0‘; ++pCh)
        {
            if(IsSwap(pBegin , pCh))
            {
            swap(*pCh,*pBegin);//交换
            Permutation(pStr, pBegin + 1);
            swap(*pCh,*pBegin);//恢复还原
            }
        }
    }
}
void swap(char a, char b)
{
    char temp = a;
    a = b;
    b = temp;
}
int main()
{
    char string[100];
    while(cin>>string)
        Permutation(string);
    return 0;
}

 

问题2：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入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。假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；而是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。

#include <iostream>
using namespace std;
#include <vector>
#include <string.h>
//函数功能 ： 从一个字符串中选m个元素
//函数参数 ： pStr为字符串， m为选的元素个数， result为选中的
//返回值 ：   无
void Combination_m(char *pStr, int m, vector<char> &result)
{
    if(pStr == NULL || (*pStr == ‘\0‘&& m != 0))
        return;
    if(m == 0) //递归终止条件
    {
        for(unsigned i = 0; i < result.size(); i++)
            cout<<result[i];
        cout<<endl;
        return;
    }
    //选择这个元素
    result.push_back(*pStr);
    Combination_m(pStr + 1, m - 1, result);
    result.pop_back();
    //不选择这个元素
    Combination_m(pStr + 1, m, result);
}
//函数功能 ： 求一个字符串的组合
//函数参数 ： pStr为字符串
//返回值 ：   无
void Combination(char *pStr)
{
    if(pStr == NULL || *pStr == ‘\0‘)
        return;
    int number = strlen(pStr);
    for(int i = 1; i <= number; i++)
    {
        vector<char> result;
        Combination_m(pStr, i, result);
    }
}
int main()
{
    char string[100];
    while(cin>>string)
        Combination(string);
    return 0;
}

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

3.打靶问题，靶一共有10环，求10次打靶命中90环的可能。

分析，每次有11种可能，1-10环，或未中

#include <iostream>
using namespace std;
#include <vector>
#include <string.h>
//函数功能 ： 求解number次打中sum环的种数
 //函数功能 ： 求解number次打中sum环的种数
//函数参数 ： number为打靶次数，sum为需要命中的环数，result用来保存中间结果，total记录种数
//返回值 ：   无
void ShootProblem_Solution1(int number, int sum, vector<int> &result, int *total)
{
    if(sum < 0 || number * 10 < sum) //加number * 10 < sum非常重要，它可以减少大量的递归，类似剪枝操作
        return;
    if(number == 1) //最后一枪
    {
        if(sum <= 10) //如果剩余环数小于10，只要最后一枪打sum环就可以了
        {
            for(unsigned i = 0; i < result.size(); i++)
                cout<<result[i]<<‘ ‘;
            cout<<sum<<endl;
            (*total)++;
            return;
        }
        else
            return;
    }
    for(unsigned i = 0; i <= 10; i++) //命中0-10环
    {
        result.push_back(i);
        ShootProblem_Solution1(number-1, sum-i, result, total); //针对剩余环数递归求解
        result.pop_back();
    }
}
//提供的公共接口
void ShootProblem(int number, int sum)
{
    int total = 0;
    vector<int> result;
    ShootProblem_Solution1(number, sum, result, &total);
    cout<<"total nums = "<<total<<endl;
}
int main()
{
    int number,sum;
    cin>>number>>sum;
   // while(cin>>number>>sum)
        ShootProblem(number,sum);
    return 0;
}

 


联系
我们