Trotter-Johnson Algorithm

A. First Edition
This is the programming assignment 4 of comp6661 and we are requested to use generate all the permutation pattern by order
of minimal change. There is well-known algorithm called Trotter-Johnson which Knuth refused to call it this way. Instead he
claimed that some people in church who ring bell discovered it long time ago.
B.The problem
Question 1: what is rank and successor of permutation [2,4,6,7,5,3,1] in both lexicographic order and minimal change order?
 
Question 3:
 
(a) (6 marks) Implement a recursive version of the Trotter-Johnson algorithm to
generate all permutations of 1, . . . , n in the minimal change order. The iterative
version can be found as Alg. 2.20 on page 63 of the textbook, or as Alg. P on
page 4 of Knuth¨s 2B.
As usual, print out a list of permutations generated for small values of n, say, up
to n = 4. For large values of n, just count the number of permutations generated,
and report the number.
What is the largest value of n that you program can handle if you are limited to
at most 5 minutes of CPU time.
(b) (3 marks) For this part, we use the permutations generated in part (a) to count the
number of permutations with no adjacent values. A permutation p = [p1, . . . , pn]
of 1, . . . , n is said to have the property of no adjacent values if there exists no
pairs of adjacent elements pi and pi+1 such that the difference of pi − pi+1 is 1 or
-1. For example, [2, 4, 1, 3] is a permutation with no adjacent values, but [1, 2, 4, 3]
is not, because of the pairs (1, 2) and the (4, 3).
Use your program from part (a) as a starting point, and count the number of
permutations of 1, . . . , n which have the no adjacent values property. Report the
numbers in a table.
(c) (1 mark) To count the number of permutations with no adjacent values, would
it be better to start with a recursive program that generates permutations in
lexicographical order, instead of the Trotter-Johnson algorithm? Why?
This is a thinking question. You do not have to implement a recursive lexicographical
permutation generating program.
C.The idea of program
 

The most interesting part of assignment of comb. algo. is that you can finish all questions by writing a program. The most

boring part of assignment of comb. algo. is that all program are based on some well-defined algorithms which makes me feel

following recipe in cooking. This may be the reason I always postpone to finish my assignment till last moment.

As for question 3-c, I use a simple backtrack to prove it is a better way to solve this kind of searching problem. However,

the result is not so encouraging.

D.The major functions
Actually when prof. demoed his program as recursive version of Trotter-Johnson, I feel a bit sad as I didn't do like that.
What I did is simply following the intuitive algorithm described in textbook which is a much easy job. And to make things
worse is that I discovered that most of my classmates are doing like that way.
E.Further improvement
 
F.File listing
 
1. permutation.cpp
 
file name: permutation.cpp
#include <iostream>
#include <ctime>

using namespace std;

const int MaxNumber=16;

//defines a callback function pointer type
typedef void (*VisitFuncType)(int*, int);

void question3_a_callback(int* array, int size);

int permSize;

int counter=0;
int non_adjacent=0;

void question3_a();
void visit(int* array, int size, bool left2right, VisitFuncType callback);
void displayArray(int* array, int size);


int permLexRank(int* array, int size);

int factor(int n);



int factor(int n)
{
	int result=1;
	for (int i=1; i<=n; i++)
	{
		result*=i;
	}
	return result;
}

void question3_b_callback(int* array, int size)
{
	bool found=false;
	for (int i=0; i<size-1; i++)
	{
		if (abs(array[i]-array[i+1])==1)
		{
			found=true;
			break;
		}
	}
	if (!found)
	{
		non_adjacent++;
		//this is used for testing
		/*
		if (permSize<=6)
		{
			displayArray(array, size);
		}
		*/
	}
}

void question3_b()
{
	int data[1];
	time_t start, finish;

	for (int i=1; i<=12; i++)
	{
		//cout<<"now test permutation of size of "<<i<<endl;
		non_adjacent=0;
		permSize=i;

		data[0]=1;
		start=time(0);
		visit(data, 1, false, question3_b_callback);
		finish=time(0);
		cout<<i<<"  "<<non_adjacent<<"  "<<finish-start<<" seconds"<<endl;
		//cout<<"in size of "<<i<<"the total number of non_adjacent permutation is:"
		//	<<non_adjacent<<endl;
		//cout<<"the total running time in seconds is:"<<finish-start<<endl;
	}
}

void question3_a()
{
	time_t start, finish;
	int data[1]={1};

	for (int i=1; i<=12; i++)
	{
		cout<<"now test permutation of size of "<<i<<endl;
		permSize=i;
		data[0]=1;
		start=time(0);
		visit(data, 1, false, question3_a_callback);
		finish=time(0);
		
		cout<<"\nthe total number of permutation is:"<<counter<<endl;
		cout<<"the total running time in seconds is:"<<finish-start<<endl;
	}
}

void insert(int* array, int size, int pos, int value)
{
	//right shift by one from pos
	for (int i=size; i>pos; i--)
	{
		array[i]=array[i-1];
	}
	array[pos]=value;
}

void displayArray(int* array, int size)
{
	cout<<"[";
	for (int i=0; i<size; i++)
	{
		cout<<array[i];
		if (i!=size-1)
		{
			cout<<",";
		}
	}
	cout<<"]\n";
}

void question3_a_callback(int* array, int size)
{
	counter++;
	if (permSize<6)
	{
		displayArray(array, size);
	}
}
		

void visit(int* array, int size, bool left2right, VisitFuncType callback)
{
	if (size==permSize)
	{
		callback(array, size);

		return ;
	}
	int local[MaxNumber];
	int pos=left2right?0:size;
	int shift=left2right?1:-1;
	int boundary=left2right?size+1:-1;
	//this is the most tricky part and I cannot figure it out for one hour
	//finally I tried and tested and get this unexplanable format
	bool temp=size%2==0?left2right:false;

	do
	{
		memcpy(local, array, size*sizeof(int));
		insert(local, size, pos, size+1);
		//visit(local, size+1, (size+pos)%2==1);
		visit(local, size+1, temp, callback);
		temp=!temp;
		pos+=shift;
	}
	while (pos!=boundary);
	/*
	if (size==MaxNumber-1)
	{
		cout<<"\n";
	}
	*/
}
		
int permRank(int* array, int size)
{
	int r=0;
	int i, j, k;
	for (j=2; j<=size; j++)
	{
		k=0; 
		i=0;
		while (array[i]!=j)
		{
			if (array[i]<j)
			{
				k++;
			}
			i++;
		}
		if (r%2==0)
		{
			r=r*j+j-k-1;
		}
		else
		{
			r=j*r+k;
		}
	}
	return r;
}

void permRankDemo()
{
	int array[MaxNumber]={1,3,2};
	cout<<permRank(array, MaxNumber)<<endl;
}

void permUnRank(int rank, int size, int*array)
{
	int r1=0, r2=0, r=rank, i, j, k;
	array[0]=1;
	for (j=2; j<=size; j++)
	{
		r1=r*factor(j)/factor(size);
		k=r1-j*r2;
		if (r2%2==0)
		{
			for (i=j-1; i>=j-k; i--)
			{
				array[i]=array[i-1];
			}
			array[j-k-1]=j;
		}
		else
		{
			for (i=j-1; i>=k+1; i--)
			{
				array[i]=array[i-1];
			}
			array[k]=j;
		}
		r2=r1;
	}
}

void permUnRankDemo()
{
	int array[MaxNumber];
	permUnRank(13, 4, array);
	displayArray(array, 4);
}

int permParity(int* array, int size)
{
	bool flags[MaxNumber];
	int i, j, c=0;
	for (i=0; i<size; i++)
	{
		flags[i]=false;
	}

	for (j=1; j<=size; j++)
	{
		if (!flags[j-1])
		{
			c++;
			flags[j-1]=true;
			i=j;
			while (array[i-1]!=j)
			{
				i=array[i-1];
				flags[i-1]=true;
			}
		}
	}
	return (size-c)%2;
}

void permSuccessor(int* array, int size)
{
	int st=0, m, d, parity;
	bool done=false;
	int local[MaxNumber];
	
	for (int i=0; i<size; i++)
	{
		local[i]=array[i];
	}
	m=size;
	while (m>1&&!done)
	{
		d=1;
		while (local[d-1]!=m)
		{
			d++;
		}
		for (i=d; i<m; i++)
		{
			local[i-1]=local[i];
		}
		parity=permParity(local, m-1);
		if (parity==1)
		{
			if (d==m)
			{
				m--;
			}
			else
			{
				int temp=array[st+d-1];
				array[st+d-1]=array[st+d];
				array[st+d]=temp;
				done=true;
			}
		}
		else
		{
			if (d==1)
			{
				m--;
				st++;
			}
			else
			{
				int temp=array[st+d-1];
				array[st+d-1]=array[st+d-2];
				array[st+d-2]=temp;
				done=true;
			}
		}
	}
	if (m==1)
	{
		cout<<"undefined\n";
		return ;
	}
}

void permSuccessorDemo()
{
	int size=4;
	int array[MaxNumber]={1,2,3,4};
	int bound=factor(size);
	for (int i=0; i<bound-1; i++)
	{
		permSuccessor(array, size);
		displayArray(array, size);
	}
}

//lexico part 
void permLexSuccessor(int* array, int size)
{
	int i, j, t;
	i=size-2;
	while (array[i+1]<array[i])
	{
		i--;
	}
	if (i<0)
	{
		cout<<"undefined\n";
		return ;
	}
	j=size-1;
	while (array[j]<array[i])
	{
		j--;
	}
	t=array[j];
	array[j]=array[i];
	array[i]=t;

	int bound=(size-i-1)/2;
	for (int k=0; k<bound; k++)
	{
		t=array[i+1+k];
		array[i+1+k]=array[size-1-k];
		array[size-1-k]=t;
	}
}

void lexSuccessorDemo()
{
	int array[MaxNumber]={1, 2, 3, 4};
	int size=factor(MaxNumber);

	displayArray(array, MaxNumber);
	for (int i=0; i<size-1; i++)
	{
		permLexSuccessor(array, MaxNumber);
		displayArray(array, MaxNumber);
	}
}

//assume contents in array starts from 1 instead of 0
int permLexRank(int* array, int size)
{
	int local[MaxNumber];
	int result=0;
	memcpy(local, array, sizeof(int)*size);
	for (int i=0; i<size; i++)
	{
		result+=(local[i]-1)*factor(size-i-1);
		for (int j=i+1; j<size; j++)
		{
			if (local[j]>local[i])
			{
				local[j]--;
			}
		}
	}
	return result;
}



void question1_a()
{
	int array[MaxNumber]={2,4,6,7,5,3,1};
	cout<<"the old array is:\n";
	displayArray(array, 7);
	cout<<"the lex rank is:"<<permLexRank(array, 7)<<endl;
	cout<<"the lex successor is:\n";
	permLexSuccessor(array, 7);
	displayArray(array, 7);
}

void test1_a()
{
	int array[MaxNumber]={1,2,3,4,5,6,7};
	for (int i=1; i<=1055; i++)
	{
		cout<<"i="<<i<<endl;
		permLexSuccessor(array, 7);
		displayArray(array, 7);
	}
}


void question1_b()
{
	int array[MaxNumber]={2,4,6,7,5,3,1};
	cout<<"the old array is:\n";
	displayArray(array, 7);
	cout<<"the Trotter-Johnson rank is:"<<permRank(array, 7)<<endl;
	cout<<"the Trotter-Johnson successor is:\n";
	permSuccessor(array, 7);
	displayArray(array, 7);
}

void test1_b()
{
	int array[MaxNumber]={1,2,3,4,5,6,7};
	displayArray(array, 7);
	for (int i=1; i<=3888; i++)
	{
		cout<<"i="<<i<<endl;
		permSuccessor(array, 7);
		displayArray(array, 7);
	}
}

void backtrack(int* array, int index, int size)
{
	if (index==size)
	{
		//displayArray(array, size);
		non_adjacent++;
		return;
	}
	bool noGood;
	for (int i=1; i<=size; i++)
	{
		noGood=abs(array[index-1]-i)==1;
	
		if (!noGood)
		{
			for (int j=0; j<index; j++)
			{
				if (array[j]==i)
				{
					noGood=true;
					break;
				}
			}
		}
		
		if (!noGood)
		{
			array[index]=i;
			backtrack(array, index+1, size);
		}
	}
}

void question3_c()
{
	time_t start, finish;

	int array[MaxNumber];
	for (int i=1; i<=12; i++)
	{
		non_adjacent=0;
		cout<<i<<" ";
		start=time(0);
		for (int j=1; j<=i; j++)
		{
			array[0]=j;
			backtrack(array, 1, i);
		}
		finish=time(0);
		cout<<" "<<non_adjacent<<" "<<finish-start<<endl;
	}
}





int main()
{
	question1_a();
	question1_b();
	question3_a();
	question3_b();
	question3_c();




	return 0;
}



A snapshot of running automated testing:
the old array is:
[2,4,6,7,5,3,1]
the lex rank is:1055
the lex successor is:
[2,4,7,1,3,5,6]
the old array is:
[2,4,6,7,5,3,1]
the Trotter-Johnson rank is:3888
the Trotter-Johnson successor is:
[2,4,6,5,7,3,1]
now test permutation of size of 1
[1]

the total number of permutation is:1
the total running time in seconds is:0
now test permutation of size of 2
[1,2]
[2,1]

the total number of permutation is:3
the total running time in seconds is:0
now test permutation of size of 3
[1,2,3]
[1,3,2]
[3,1,2]
[3,2,1]
[2,3,1]
[2,1,3]

the total number of permutation is:9
the total running time in seconds is:0
now test permutation of size of 4
[1,2,3,4]
[1,2,4,3]
[1,4,2,3]
[4,1,2,3]
[4,1,3,2]
[1,4,3,2]
[1,3,4,2]
[1,3,2,4]
[3,1,2,4]
[3,1,4,2]
[3,4,1,2]
[4,3,1,2]
[4,3,2,1]
[3,4,2,1]
[3,2,4,1]
[3,2,1,4]
[2,3,1,4]
[2,3,4,1]
[2,4,3,1]
[4,2,3,1]
[4,2,1,3]
[2,4,1,3]
[2,1,4,3]
[2,1,3,4]

the total number of permutation is:33
the total running time in seconds is:0
now test permutation of size of 5
[1,2,3,4,5]
[1,2,3,5,4]
[1,2,5,3,4]
[1,5,2,3,4]
[5,1,2,3,4]
[5,1,2,4,3]
[1,5,2,4,3]
[1,2,5,4,3]
[1,2,4,5,3]
[1,2,4,3,5]
[1,4,2,3,5]
[1,4,2,5,3]
[1,4,5,2,3]
[1,5,4,2,3]
[5,1,4,2,3]
[5,4,1,2,3]
[4,5,1,2,3]
[4,1,5,2,3]
[4,1,2,5,3]
[4,1,2,3,5]
[4,1,3,2,5]
[4,1,3,5,2]
[4,1,5,3,2]
[4,5,1,3,2]
[5,4,1,3,2]
[5,1,4,3,2]
[1,5,4,3,2]
[1,4,5,3,2]
[1,4,3,5,2]
[1,4,3,2,5]
[1,3,4,2,5]
[1,3,4,5,2]
[1,3,5,4,2]
[1,5,3,4,2]
[5,1,3,4,2]
[5,1,3,2,4]
[1,5,3,2,4]
[1,3,5,2,4]
[1,3,2,5,4]
[1,3,2,4,5]
[3,1,2,4,5]
[3,1,2,5,4]
[3,1,5,2,4]
[3,5,1,2,4]
[5,3,1,2,4]
[5,3,1,4,2]
[3,5,1,4,2]
[3,1,5,4,2]
[3,1,4,5,2]
[3,1,4,2,5]
[3,4,1,2,5]
[3,4,1,5,2]
[3,4,5,1,2]
[3,5,4,1,2]
[5,3,4,1,2]
[5,4,3,1,2]
[4,5,3,1,2]
[4,3,5,1,2]
[4,3,1,5,2]
[4,3,1,2,5]
[4,3,2,1,5]
[4,3,2,5,1]
[4,3,5,2,1]
[4,5,3,2,1]
[5,4,3,2,1]
[5,3,4,2,1]
[3,5,4,2,1]
[3,4,5,2,1]
[3,4,2,5,1]
[3,4,2,1,5]
[3,2,4,1,5]
[3,2,4,5,1]
[3,2,5,4,1]
[3,5,2,4,1]
[5,3,2,4,1]
[5,3,2,1,4]
[3,5,2,1,4]
[3,2,5,1,4]
[3,2,1,5,4]
[3,2,1,4,5]
[2,3,1,4,5]
[2,3,1,5,4]
[2,3,5,1,4]
[2,5,3,1,4]
[5,2,3,1,4]
[5,2,3,4,1]
[2,5,3,4,1]
[2,3,5,4,1]
[2,3,4,5,1]
[2,3,4,1,5]
[2,4,3,1,5]
[2,4,3,5,1]
[2,4,5,3,1]
[2,5,4,3,1]
[5,2,4,3,1]
[5,4,2,3,1]
[4,5,2,3,1]
[4,2,5,3,1]
[4,2,3,5,1]
[4,2,3,1,5]
[4,2,1,3,5]
[4,2,1,5,3]
[4,2,5,1,3]
[4,5,2,1,3]
[5,4,2,1,3]
[5,2,4,1,3]
[2,5,4,1,3]
[2,4,5,1,3]
[2,4,1,5,3]
[2,4,1,3,5]
[2,1,4,3,5]
[2,1,4,5,3]
[2,1,5,4,3]
[2,5,1,4,3]
[5,2,1,4,3]
[5,2,1,3,4]
[2,5,1,3,4]
[2,1,5,3,4]
[2,1,3,5,4]
[2,1,3,4,5]

the total number of permutation is:153
the total running time in seconds is:0
now test permutation of size of 6

the total number of permutation is:873
the total running time in seconds is:0
now test permutation of size of 7

the total number of permutation is:5913
the total running time in seconds is:0
now test permutation of size of 8

the total number of permutation is:46233
the total running time in seconds is:0
now test permutation of size of 9

the total number of permutation is:409113
the total running time in seconds is:0
now test permutation of size of 10

the total number of permutation is:4037913
the total running time in seconds is:1
now test permutation of size of 11

the total number of permutation is:43954713
the total running time in seconds is:11
now test permutation of size of 12

the total number of permutation is:522956313
the total running time in seconds is:149
1 1 0 seconds
2 0 0 seconds
3 0 0 seconds
4 2 0 seconds
5 14 0 seconds
6 90 0 seconds
7 646 0 seconds
8 5242 0 seconds
9 47622 1 seconds
10 479306 1 seconds
11 5296790 15 seconds
12 63779034 187 seconds
1 1 0
2 0 0
3 0 0
4 2 0
5 14 0
6 90 0
7 646 0
8 5242 0
9 47622 0
10 479306 1
11 5296790 14
12 63779034 281
Press any key to continue
			
				 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)