1、算法简述
简单地说:全排列就是从第一个数字起每个数分别与它后面的数字交换。
E.g:E = (a , b , c),则 prem(E)= a.perm(b,c)+ b.perm(a,c)+ c.perm(a,b)
然后a.perm(b,c)= ab.perm(c)+ ac.perm(b)= abc + acb.依次递归进行。
#include<iostream>
using namespace std; void Swap(char *a,char *b)
{
char tmp=*a;
*a=*b;
*b=tmp;
} void AllRange(char *pszStr,int k,int m)
{
if(k==m)
{
static int s_i=;
printf("%s\n",s_i++,pszStr);
}
else
{
for(int i=k;i<=m;i++)
{
Swap(pszStr+i,pszStr+k);
AllRange(pszStr,k+,m);
Swap(pszStr+i,pszStr+k);
}
}
} void Foo(char *pszStr)
{
AllRange(pszStr,,strlen(pszStr)-);
} int main()
{
printf("全排列的递归实现:\n");
char szTextStr[] = "";
printf("%s的全排列如下:\n", szTextStr);
Foo(szTextStr);
system("pause");
return ;
}
结果:
全排列的递归实现:
123的全排列如下:
如果输入122:,结果为
全排列的递归实现:
122的全排列如下:
显然不符合题目要求。
2、代码改进
去掉重复符号的全排列:在交换之前可以先判断两个符号是否相同,不相同才交换,这个时候需要一个判断符号是否相同的函数。
#include<iostream>
using namespace std; void Swap(char *a,char *b)
{
char tmp=*a;
*a=*b;
*b=tmp;
} //在pszStr数组中,[nBegin,nEnd)中是否有数字与下标为nEnd的数字相等
bool IsSwap(char *pszStr, int nBegin, int nEnd)
{
for (int i = nBegin; i < nEnd; i++)
if (pszStr[i] == pszStr[nEnd])
return false;
return true;
} //k表示当前选取到第几个数,m表示共有多少数.
void AllRange(char *pszStr,int k,int m)
{
if(k==m)
{
static int s_i=;
printf("%s\n",s_i++,pszStr);
}
else
{
for(int i=k;i<=m;i++)
{
if (IsSwap(pszStr,k,i))
{
Swap(pszStr+i,pszStr+k);
AllRange(pszStr,k+,m);
Swap(pszStr+i,pszStr+k);
}
}
}
} void Foo(char *pszStr)
{
AllRange(pszStr,,strlen(pszStr)-);
} int main()
{
printf("全排列的递归实现:\n");
char szTextStr[] = "";
printf("%s的全排列如下:\n", szTextStr);
Foo(szTextStr);
system("pause");
return ;
}
结果如下:
全排列的递归实现:
122的全排列如下: