comb1.cpp

这是一个生成组合序列的程序,而且是非递归的,代码非常精简,速度很快,序列是字典序的.

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

void comb(int n,int k,int *a)
{
	int *s=new int[k+1],tp=k;
	for(int i=0;i<=k;i++)
		s[i]=i-1;
	while(true)
	{
		for(i=1;i<=k;i++)
			cout<<a[s[i]]<<' ';
		cout<<endl;
		while(s[tp]+k+1-tp>=n)
			tp--;
		if(tp<1)
			break;
		s[tp]++;
		while(tp<k)
		{
			int temp=s[tp];
			s[++tp]=temp+1;
		}
	}
}

void main()
{
	int n,k;
	cin>>n>>k;
	int *a=new int[n];
	for(int i=0;i<n;i++)
		a[i]=i+1;
	clock_t start=clock(),finish;
	cout<<"Combination list:"<<endl;
	comb(n,k,a);
	finish=clock();
	double total=(double)(finish-start);
	cout<<"程序耗时: "<<total<<endl;
}