数组全排列算法（一）字符串数组全排列――逐个追加组合算法 - c++编程基础

算法题：用你熟悉的编程语言，设计如下功能的函数：

输入一个字符串，输出该字符串中所有字母的全排列。程序请适当添加注释。

C++函数原型： void Print（const char *str）

输入样例： abc

分析：

n个字符串的全排列就是n!，而由于2^32=4294967296，12!=479001600，11!=39916800，

本文讨论的算法在限制n<12，关于n>=12的后续讨论。

另外这里输入的字符也是不重复的，重复的相对复杂，后续可以讨论。

思想是这样的:比如输入字符串是abc，定义vectorA、vectorB。

先取a放到vectorA中，

然后取b，与进行组合，则有ba，ab，放到vectorB中，同时清空vectorA。

再取c，与vectorB里的ba，ab分别组合。依次得到cba，bca，bac和cab，acb，abc，放到vectorA中。

最后遍历不为空的vector，打印出组合结果。

这个算法就是逐个追加组合算法。

代码实现如下：

#define MAXNUM 12  
  
//定义2个放结果的vector，交替使用。  
std::vector g_vecA;  
std::vector g_vecB;  
  
void Print(const char *str)  
{  
    char Temp;  
    int nLen = strlen(str);  
    char Temp0[2];  
    Temp0[0]=str[0];  
    Temp0[1]='\0';  
    g_vecA.push_back(Temp0);//先把第一个字母放到容器里  
  
    vector::iterator itor;  
    for (int i=1; i=g_vecB.begin(); itor--)  
            {  
                char* p = *itor;  
                g_vecB.erase(itor);  
            }  
            g_vecB.clear();  
        }  
        else  
        {  
            //遍历A中的元素  
            for(itor=g_vecA.begin();itor!=g_vecA.end();itor++)   
            {  
                char* p = *itor;  
                  
                int nSize = strlen(p);  
                  
                //从0到nSize位置放Temp  
                for (int j=0; j=g_vecA.begin(); itor--)  
            {  
                char* p = *itor;  
                g_vecA.erase(itor);  
            }  
            g_vecA.clear();  
        }  
    }  
  
    int nCount = 0;  
  
    //打印所有组合  
    if (g_vecA.size()==0)  
    {  
        for(itor=g_vecB.begin();itor!=g_vecB.end();itor++)   
        {  
            nCount ++;  
            char* p = *itor;  
            cout << p << ", ";  
  
            if (nCount%10 == 0)  
            {  
                cout << endl;  
            }  
  
            delete p;  
            p=NULL;  
        }  
    }  
    else  
    {  
        for(itor=g_vecA.begin();itor!=g_vecA.end();itor++)   
        {  
            nCount ++;  
            char* p = *itor;  
            cout << p << ", ";  
              
            if (nCount%10 == 0)  
            {  
                cout << endl;  
            }  
  
            delete p;  
            p=NULL;  
        }  
    }  
  
    g_vecA.clear();  
    g_vecB.clear();  
  
    cout << endl;  
  
}

int main()    
{     
    g_vecA.clear();  
    g_vecB.clear();  
    char str[MAXNUM];  
  
    char Temp[256];  
    scanf("%s", Temp);  
  
    if (strlen(Temp)>=12)  
    {  
        cout<<"字符串长度是1-11。" <

测试结果：

当输入abc时：

cba, bca, bac, cab, acb, abc,

当输入abcd时：

dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac,

badc, bacd, dcab, cdab, cadb, cabd, dacb, adcb, acdb, acbd,

dabc, adbc, abdc, abcd,