重庆巴南万达:排列组合程序

两个异曲同工的排列组合程序

program1
#include<iomanip.h>
#include<windows.h>
#include<string.h>
#include<stdio.h>
template<class T>
void swap(T& a,T& b)
{
T c;
c=a;
a=b;
b=c;
}
template<class T>
void perm(T* s,int k,int m,int& num)
{
for(int i=k;i<=m;i++)
{
swap(s[i],s[k]);
perm(s,k+1,m,num);
swap(s[i],s[k]);
}
if(k==m)
{
for(int j=0;j<=m;j++)
cout<<s[j]<<" ";
cout<<endl;
num++;
}
}
void main()
{
int num=0;
cout<<"输入字符序列:";
char* s=new char[30];
cin>>s;
DWORD time=GetTickCount();
perm(s,0,strlen(s)-1,num);
time=GetTickCount()-time;
cout<<"不同序列总个数是"<<num<<endl;
cout<<endl;
if(time<=10)
cout<<"程序运行的时间小于10ms"<<endl;
else
cout<<"程序运行的时间是"<<time<<"ms"<<endl;

getchar();

}

program2
#include<iomanip.h>
#include<stdio.h>
#include<string.h>
#include<windows.h>
void formturn(int index,char * s,char * mys,int& num)
{
char * s1=new char [30];
char tmp;
unsigned int i;
for( i=0;i<strlen(s);i++)
{
tmp=s[i];
mys[index]=s[i];
s[i]=0;
strcpy(s1,s);
strcat(s1,&s[i+1]);
s[i]=tmp;
formturn(index+1,s1,mys,num);
}
if(strlen(s)==0)
{
cout<<mys<<endl;
num++;
}
}
void main()
{
int num=0;
void formturn(int index,char * s,char * mys,int& num);
char * s=new char [30];
char * mys=new char [30];
cout<<"输入字符序列:";
cin>>s;
DWORD time=GetTickCount();
strcpy(mys,s);
formturn(0,s,mys,num);
time=GetTickCount()-time;
if(time<=10)
cout<<"程序运行的时间小于10ms"<<endl;
else
cout<<"程序运行的时间是"<<time<<"ms"<<endl;
cout<<endl;
cout<<"不同的组合序列数为"<<num<<endl;
getchar();

}