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.
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.
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