全排列

#include “stdafx.h”
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
#include <algorithm>
using namespace ::std;
void Foo(const char *str);           //stl
void Foo2(const char *str);          //recursion
void foo2( char *str,int position,int strlen ,int &count);
void Foo3(const char *str);          //loop
int main(int argc, char *argv[])
{
unsigned long start = ::GetTickCount();
Foo(”abcdefg”);
unsigned long end = ::GetTickCount();
unsigned long worktime1 = end - start;
start = ::GetTickCount();
Foo2(”abcdefg”);
end = ::GetTickCount();
unsigned long worktime2 = end - start;
start = ::GetTickCount();
Foo3(”abcdefg”);
end = ::GetTickCount();
unsigned long worktime3 = end - start;
cout< <”use stl time = “<<worktime1 <<endl;
cout<<”use recursion time = “<<worktime2 <<endl;
cout<<”use loop time = “<<worktime3 <<endl;
system(”pause”);
return 0;
}
void Foo(const char *str)
{
int n=strlen(str),count=0;
vector<char> a(n);
for(int i=0; i<n ; i++)
a[i]=str[i];
vector<char>::iterator start, end;
ostream_iterator<char> outIt(cout, “”);
start = a.begin();
end = a.end();
do {
count++;
copy(start, end, outIt) ;
cout < < endl ;
} while(next_permutation(start, end));
cout<<count<<endl;
}
void Foo2(const char *str)
{
int n=strlen(str),count=0;
char *mystr = (char *)malloc(n*sizeof(char));
memcpy(mystr , str ,n);
 
foo2(mystr , 0 , n ,count);
cout<<count<<endl;
free(mystr);
}
void foo2(char *str,int position,int strlen ,int &count)
{
if(position == strlen)
{
cout<<str<<endl;
count ++;
}
else
{
for(int i = position; i < strlen; i++)
{
swap(*(str + i) , *(str + position));
foo2(str,position+1,strlen,count);
swap(*(str + i) , *(str + position));
}
}
}
void Foo3(const char *str)
{
int len = strlen(str);
int * range = new int[len];
int cont, i, j, counter = 0;
memset(range, 0, len*sizeof(int));
while(1)
{
for(i=0; i<len; i++)
{
if(++range[i]>=len)
range[i] = 0;
else
break;
}
if (i==len)
{
break;
}
for(i=0,cont=0; i<len -1; i++)
{
for(j=i+1; j<len; j++)
{
if(range[i] == range[j])
{
cont=1;
break;
}
}
if (cont == 1)
{
break;
}
}
if (cont) continue;
for(i=0; i<len; i++)
{
printf(”%c”, str[range[i]]);
}
printf(”n”);
++counter;
}
delete [] range;
cout<<counter<<endl;
}