Trotter-Johnson Algorithm
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.
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.
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.
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
