全排列问题的递归算法.cpp

递归和分治法解一系列经典算法

//全排列问题的递归算法

#include <iostream.h>
#define N 20
int count=0;
void Perm(int list[],int k,int m)
{
	int i,temp;
	if(k==m)
	{
		cout<<++count<<": ";
		for(i=0; i<=m; i++) cout<<" "<<list[i];
		cout<<endl;
	}
	else
		for(i=k; i<=m; i++)
		{
			temp=list[k];
			list[k]=list[i];
			list[i]=temp;
			Perm(list,k+1,m);
			temp=list[k];
			list[k]=list[i];
			list[i]=temp;
		}
}

void main()
{
	int i,n=0,list[N];
	cout<<"请输入1个正整数n: ";
	while(n<1) cin>>n;
	if(n>N) n=N;
	for(i=0; i<n; i++) list[i]=i+1;
	Perm(list,0,n-1);
}