全排列打印
全排列的要求:
输入:字符串"abc"。
输出:如下图示,
思路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:全排列的字典树实现
待笔者研究透字典树后深入写出该算法。
作者:铭毅天下
来源:CSDN
原文:https://blog.csdn.net/laoyang360/article/details/8097375
版权声明:本文为博主原创文章,转载请附上博文链接!