m2.cpp

//给定整数n

#include <stdio.h>

//给定整数n，产生所有[2n]上的匹配（matching）
//将其视为一个所有块大小均为2的集合分拆
//以a_i表示其第i个元素所在的集合号
//输出格式为 a1 a2 a3 ...
//满足
//a_{i+1} <= max { a1,a2,...a_i } + 1
//时间大约20s

//算法思想如下：
//初始集合编号为112233...，依次产生新的分拆
//并且以数组bi表示ai是第几次出现，
//首次出现为1，第二次出现为0
//直至找不到p使得a[p]<a[p+1]且b[p]==0

//产生新的分拆方法为：
//1. 找到a[p]<=a[p+1]且b[p]==0
//2. 将a[p]和它后面比它小的最大元素x互换
//3. 将a[p]后面的元素顺序排列

//在1中有两种情况，一种是首次a[i]<=a[i+1]的位置满足b[p]==0
//此时可以直接将a[p]和x互换，再重排后面的元素
//注意到此时b[i]从i=p开始均为0，不需要重新对b赋值。

//另一种情况是首次a[i]<=a[i+1]的位置满足b[p]==1
//则向前查找首次b[p]==0的位置，必然有a[p]<a[p+1]
//记录下p位置之后满足b[i]==1的位置数r
//则p位置之后的元素必定为
//n-r+1,n-r+2,...,n,n,n-1,...n-r+1,a[2n-2r-p+1],...,a[2n]
//我们首先将a[p]和x=a[q]互换
//然后再分两种情况讨论：

//一种是a[q]=n-r+1，即q=p+2r，此时p及其后的元素应该排成
//n-r+1, a[2n],...,a[2n-2r-p+1], a[p],n-r+1, n-r+2,n-r+2, ... n,n
//相应的b为1, 0,...,0, 0,0, 1,0, ..., 1,0

//另一种是a[q]<n-r+1，此时p及其后的元素排成
//a[q], a[2n],...,a[2n-2r-p+1], n-r+1,n-r+1, n-r+2,n-r+2, ... n,n
//相应的b为0, 0,...,0, 1,0, 1,0, ..., 1,0


void main()
{

	int i,p,q,r,n,tmp;
	long int tnum;

	int a[21],b[21];
	
	n=10;

	for (i=1;i<=n;i++) 
	{
		a[2*i-1]=i; a[2*i]=i; b[2*i-1]=1; b[2*i]=0;
	}

	tnum=0;

	while (n>0) 
	{	
		
		//输出匹配
		tnum++;
		/*for (i=1;i<=n;i++)
			printf("%d%d",a[2*i-1],a[2*i]);
		printf("\n");*/

		//下一个匹配
		p=2*n-1;
		while ((p>0) && (a[p]>a[p+1])) p--;  //查找第一个顺序位。

		if (p==0) break;
		
		if (b[p]==1)
		{
			r=1; p--;
			while((p>0) && (b[p]==1)) 
			{
				p--; r++;
			}

			if (p==0)
				break;
			else
			{
				q=p+2*r;
				while ((q<2*n) && a[q+1]>a[p]) q++;
				
				//交换a[p]和a[q]
				//b[p]=b[q]=0，不需要变化
				tmp=a[p]; a[p]=a[q]; a[q]=tmp; 

				if (q==p+2*r)
				{
					b[p]=1;

					//利用对换将后面元素排成顺序
					for (i=1;i<=(2*n-p)/2;i++)
					{
						tmp=a[p+i]; a[p+i]=a[2*n+1-i]; a[2*n+1-i]=tmp;
					}

					//a[q]后面有2n-q个元素，再加上a[p]，共2n-q+1个元素
					for (i=1;i<=2*n-q+1;i++)	b[p+i]=0;

					a[2*n-2*r+2]=a[p];
					b[2*n-2*r+2]=0;


					for (i=1;i<=r-1;i++)
					{
						a[2*n+2-2*i]=n+1-i;
						a[2*n+1-2*i]=n+1-i;
						b[2*n+2-2*i]=0;
						b[2*n+1-2*i]=1;
					}
				}
				else
				{
					b[p]=0;
					
					//利用对换将后面元素排成顺序
					for (i=1;i<=(2*n-p)/2;i++)
					{
						tmp=a[p+i]; a[p+i]=a[2*n+1-i]; a[2*n+1-i]=tmp;
					}

					for (i=1;i<=2*n-2*r-p;i++)	b[p+i]=0;

					for (i=1;i<=r;i++)
					{
						a[2*n+2-2*i]=n+1-i; a[2*n+1-2*i]=n+1-i;
						b[2*n+2-2*i]=0; b[2*n+1-2*i]=1;
					}
				}
			}
		}
		else
		{
			q=p+1;
			while ((q<2*n) && (a[q+1]>a[p])) q++;

			//将p和q互换
			tmp=a[p]; a[p]=a[q]; a[q]=tmp; 
				
			//利用对换将后面元素排成顺序
			//此时b[i]从p开始全部为0，不需要重新赋值。
			for (i=1;i<=(2*n-p)/2;i++)
			{
				tmp=a[p+i]; a[p+i]=a[2*n+1-i]; a[2*n+1-i]=tmp;
			}

		}
	} 
	printf("%d\n",tnum);
}