perm1.cpp

这是一个生成全排列的程序,采用最小变化算法,相邻两个序列之间只有两个数的次序不同,每交换两个数,便形成一个新的序列,速度非常快.

#include<iostream.h>
#include<time.h>

void swap(int &a,int &b)
{
	int temp=a;
	a=b;
	b=temp;
}

void print(int *a,int *s,int n)
{
	for(int i=1;i<=n;i++)
		cout<<a[s[i]]<<' ';
	cout<<endl;
}

void perm(int *a,int n)
{
	int *s=new int[n+2],tp=n;
	for(int i=0;i<=n;i++)
		s[i]=i;
	s[i]=0;
	while(true)
	{
		print(a,s,n);
		while(s[tp]>s[tp+1])
			tp--;
		if(tp<1)
			break;
		for(i=tp+1;i<(n+tp+2)/2;i++)
			swap(s[i],s[n+tp+1-i]);
		for(i=tp+1;s[i]<s[tp];i++);
		swap(s[i],s[tp]);
		tp=n;
	}
}

void main()
{
	int n;
	cin>>n;
	int *a=new int[n+1];
	for(int i=1;i<=n;i++)
		a[i]=i;
	cout<<"Permutation lists:"<<endl;
	clock_t start=clock(),finish;
	perm(a,n);
	finish=clock();
	double total=(double)(finish-start);
	cout<<total<<endl;
}