全排列打印

简介: 全排列打印实现。

全排列打印

全排列的要求:

输入:字符串"abc"。

输出:如下图示,

image.png

思路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;
}

思路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;
}

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

image.png

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

作者:铭毅天下
来源:CSDN
原文:https://blog.csdn.net/laoyang360/article/details/8097375
版权声明:本文为博主原创文章,转载请附上博文链接!

相关文章
|
7月前
数组遍历输出
数组遍历输出
32 1
|
2月前
|
人工智能
打印出杨辉三角形
打印出杨辉三角形。
68 17
|
7月前
逆序数打印
该内容是关于编程计算正整数的逆序数。用户输入一个正整数,程序需输出其逆序数,即数字顺序反转后的数。文章中包含两张图片作为示例,但图片数据未显示。
43 0
|
7月前
杨辉三角问题(打印空格版)
特点:1、每个数字等于上一行的左右两个数字之和。2、第n+1行的第i个数等于第n行的第i-1个数和第i个数之和,即 C(n+1,i)=C(n,i)+C(n,i-1)。下面我们通过两种不同的办法实现杨辉三角
7-164 打印杨辉三角
7-164 打印杨辉三角
60 0
|
算法
递归实现数字正序打印。(分析)
递归实现数字正序打印。(分析)
907 0
递归实现数字正序打印。(分析)
用for循环打印乘法口诀表
用for循环打印乘法口诀表
116 0
用for循环打印乘法口诀表
AcWing 815. 打印字符串
AcWing 815. 打印字符串
122 0
AcWing 815. 打印字符串
AcWing 764. 输出字符串
AcWing 764. 输出字符串
52 0
AcWing 764. 输出字符串
AcWing 812. 打印数字
AcWing 812. 打印数字
51 0
AcWing 812. 打印数字