C++全排列實現代碼

思路1——全排列的遞歸實現核心思想：

比如對于字符串”abc”，

第一步：求所有可能出現在第一個位置的字符即：a,b,c。

使用方法：把第一個字符和后面的b、c字符進行交換。

第二步：把第一個字符后面的所有字符仍然看成兩部分，即后面的第一個字符及除此之外的其他字符。然后完成后面的第一個字符與其他字符的交換。比如：第2個位置的b與第3個位置c的交換。

第三步：依次遞歸，直到末尾的’\0’為止。

static int g_sCnt= 0;

//permutation的重載版本.
voidpermutation(char pStr, char pBegin)
{
       if(pBegin == '\0')
       {
              ++g_sCnt;
              cout << pStr << endl;
       }
       else
       {
              for(char pCh = pBegin; pCh != '\0'; ++pCh)
              {
                     //從第一個字符依次和后面的字符進行交換.
                     char temp = pCh;
                     pCh = pBegin;
                     *pBegin = temp;

                 permutation(pStr,pBegin+1);

                 //交換回原樣，以便再遞歸處理后面的字符.
                 temp = *pCh;
                 *pCh = *pBegin;
                 *pBegin = temp;

          }//end for
   }//end else

}
//全排列處理函數
voidpermutation(char* pStr)
{
    if(pStr== NULL)
        {
              return;
        }
       else
        {
              permutation(pStr,pStr);
        }
}
int main()
{
    char strSrc[] = "abcd";
    permutation(strSrc);
    cout<< "共 " << g_sCnt << " 種排列!" <<endl;
return 0;
}
 </pre> 

 思路2——全排列的STL實現：

 

 有時候遞歸的效率使得我們不得不考慮除此之外的其他實現，很多把遞歸算法轉換到非遞歸形式的算法是比較難的，這個時候我們不要忘記了標準模板庫STL已經實現的那些算法，這讓我們非常輕松。

 

 STL有一個函數next_permutation()，它的作用是如果對于一個序列，存在按照字典排序后這個排列的下一個排列，那么就返回true且產生這個排列，否則返回false。

 

 注意，為了產生全排列，這個序列要是有序的，也就是說要調用一次sort。

 

 實現很簡單，我們看一下代碼：
void permutation(char* str)
{
       int length = strlen(str);


   //第1步：排序
sort(str,str+length);

   //第2步：調用函數next_permutation
do
{
    for(int i=0; i<length; i++)
          {
                 cout<<str[i];
          }
    cout << endl;
}while(next_permutation(str,str+length));


}
int main()
{
    char str[] = "acb";
    permutation(str);

return 0;

}</pre>