数组全排列算法（一）字符串数组全排列——逐个追加组合算法

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

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

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<char*> g_vecA;  
std::vector<char*> 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<char*>::iterator itor;  
    for (int i=1; i<nLen; i++)  
    {  
        Temp = str[i];  
  
        if (g_vecA.size()==0)  
        {  
            //遍历B中的元素  
            for(itor=g_vecB.begin();itor!=g_vecB.end();itor++)   
            {  
                char* p = *itor;  
  
                int nSize = strlen(p);  
                //从0到nSize位置放Temp  
                for (int j=0; j<nSize+1; j++)  
                {  
                    char* q = new char[nSize+2];//如果放在循环外面则最后都是一个值  
                    for (int k=0; k<j; k++)  
                    {  
                        q[k]=p[k];  
                    }  
  
                    q[j]=Temp;  
  
                    for (int m=j+1; m<nSize+1; m++)  
                    {  
                        q[m]=p[m-1];  
                    }  
  
                    q[nSize+1]='\0';  
                    g_vecA.push_back(q);  
                }  
            }  
  
            for (itor = g_vecB.end()-1; itor>=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<nSize+1; j++)  
                {  
                    char* q = new char[nSize+2];  
                    for (int k=0; k<j; k++)  
                    {  
                        q[k]=p[k];  
                    }  
                      
                    q[j]=Temp;  
                      
                    for (int m=j+1; m<nSize+1; m++)  
                    {  
                        q[m]=p[m-1];  
                    }  
                    q[nSize+1]='\0';  
                    g_vecB.push_back(q);  
                }  
            }  
  
            for (itor = g_vecA.end()-1; itor>=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。" <<endl;  
  
        return 0;  
    }  
    else  
    {  
        strcpy(str, Temp);  
    }  
  
    Print(str);  
  
    return 0;    
}

测试结果：

当输入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,

补充：软件开发 , C++ ,