当前位置:编程学习 > C/C++ >>

全排列打印

全排列打印
全排列的要求:

输入:字符串"abc"。

输出:如下图示,

 

 

思路1——全排列的递归实现核心思想:

比如对于字符串”abc”,

第一步:求所有可能出现在第一个位置的字符即:a,b,c。

使用方法:把第一个字符和后面的b、c字符进行交换。

第二步:把第一个字符后面的所有字符仍然看成两部分,即后面的第一个字符及除此之外的其他字符。然后完成后面的第一个字符与其他字符的交换。比如:第2个位置的b与第3个位置c的交换。

第三步:依次递归,直到末尾的’\0’为止。

 

全排列的递归实现:                                    

[cpp] 
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; 

思路2——全排列的STL实现:

有时候递归的效率使得我们不得不考虑除此之外的其他实现,很多把递归算法转换到非递归形式的算法是比较难的,这个时候我们不要忘记了标准模板库STL已经实现的那些算法,这让我们非常轻松。

STL有一个函数next_permutation(),它的作用是如果对于一个序列,存在按照字典排序后这个排列的下一个排列,那么就返回true且产生这个排列,否则返回false。

注意,为了产生全排列,这个序列要是有序的,也就是说要调用一次sort。

实现很简单,我们看一下代码:

     

[cpp] 
 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; 

思路3:全排列的字典树实现

 

待笔者研究透字典树后深入写出该算法。

补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,