c_arrange_序数法.cpp

组合数学中的原理实现

#include<iostream.h>

//定义排序这个类
void CPermute()
	{   
		int a[20]={0};
		int b[20]={0};
		int n=0;
		int factrial=1;
		cout<<"请输入你想排列的个数:"<<endl;
		cin>>n;
		//计算所要进行的全排列的次数
		for(int i=1;i<=n;i++)
			factrial*=i;
		cout<<factrial;
		cout<<endl;
		//对n个数进行全排列
		for(int j=0;j<factrial;j++)
		{
			//计算出1到n!-1个数每个数所对应的一个序数组
        	int shang=j,index=0;
			do
			{
				a[index]=shang%(index+2);
				shang/=(index+2);
				index++;
			}while(shang);
			//由上一步所求的序数组来确定一个排列，a[k]确定k+1的位置
			for(int s=0;s<(n-1);s++)
			{
				cout<<a[s]<<",";
			}
		for(int k=n-1;k>0;k--)
			{
				int index=k;
				int spacecount=0;
				while(a[k]>spacecount||b[index]!=0)
				{
					if(b[index]==0)spacecount++;
					index--;
				}
				b[index]=k+1;
			}
			index=n; 
			while(b[index]!=0)
				index--;
			   b[index]=1;
			//输出结果
			   for(int m=0;m<n;m++)
			   {
				   cout<<b[m]<<",";
			   }
			   cout<<endl;
		}
	}


void main()
{
	CPermute();
}