jonhsontrotter.cpp

对于给定的整数$n$

#include<stdio.h>

void main()
{
	const MAXN=10;
	int a[MAXN], direct[MAXN], pos[MAXN], expos, level, tmp, i,n;
	
	printf("Please enter an integer between 1 and %d: ",MAXN-1);
	scanf("%d",&n);

	for(i=0;i<=n;i++)		//a[0],pos[0],direct[0]只作为结束标记用
	{
		a[i]=i; direct[i]=-1; pos[i]=i; 
		//a[i]用来记录置换，direct[i]用来记录变换方向
		//pos[i]用于记录变换位置
	}
	
	do
	{
		for(i=1;i<=n;i++)
			printf("%d",a[i]);
		printf("\t");

		//通过相邻对换产生新的置换
		//对换的位置由pos确定
		//level记录变换的层数
		level=n;
		pos[n]=pos[n]+direct[n];
		expos=0;

		while (pos[level]==0 || pos[level]==level) 
		{
			if (direct[level]==-1) expos++;		//前面有一个大元素

			direct[level]=-direct[level];			//变方向

			level--;
			pos[level]=pos[level]+direct[level];
		}

		expos=expos+pos[level];

		tmp=a[expos];
		a[expos]=a[expos+1];
		a[expos+1]=tmp;
	
	} while(level>0);  //当达到最内层变换时结束

	printf("\n");

}