调用C++标准库中的函数实现：
#include <algorithm>
#include <iostream>
#include "windows.h"
using namespace std;
template <typename BidirectionalIterator,typename T>
void permutation(BidirectionalIterator first, BidirectionalIterator last,T s)
{
sort(first,last);
do{
for(BidirectionalIterator i(first);i!=last;++i)
{
cout << *i; cout << s;
}
cout << endl;
}while (next_permutation(first, last));
}
int main()
{
int A[] = {1,2,3,4,5,6,7,8};
const int N = sizeof(A) / sizeof(int);
int nTime = GetTickCount();
permutation(A, A+N ,",");
nTime = GetTickCount() - nTime;
return 0;
}
非递归实现：
#include "stdio.h"
#include "iostream.h"
#include "Windows.h"
void func(int n,char * a);
int main()
{
char arr[]="12345678";
int nTime = GetTickCount();
func(8,arr);
nTime = GetTickCount() - nTime;
return 0;
}
void func(int n,char * a) //an array a[n]
{
int *i=new int[n];
int c=0,j;
i[c]=-1;
for(;i[0]<n;)
{
if(++i[c]<n)
{
for(j=0;j<c&&i[j]!=i[c];j++);
if(j==c)
{
if(c+1<n)
{
i[++c]=-1;
// continue;
}
else
{
for(int j=0;j<n;j++)
cout<<a[i[j]]<<",";
cout<<endl;
}
}
}
else
c--;
}
}
递归算法：
#include <iostream.h>
#include "windows.h"
#define MAXN 100
int a[MAXN];
int flag[MAXN];
void comb(int m, int k, int s)
{
int i;
if (s >= k)
{
for (i = 0; i < k; i++)
cout << a[i] << " ";
cout << endl;
}
else
{
for (i = 1; i <= m; i++)
if (0 == flag[i])
{
flag[i]=1;
a[s]=i;
comb(m,k,s+1);
a[s]=0;
flag[i]=0;
}
}
}
void main()
{
int i;
for (i=0; i<MAXN; i++)
a[i]=flag[i]=0;
int nTime = GetTickCount();
comb(8,8,0);
//comb(m,n,0) 表示求m个选n个的排列
nTime = GetTickCount() - nTime;
return;
}
以8个数的全排列来测试，递归最快，调用库函数最慢。