combinatorial algorithm

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