#include<stdio.h> #include<stdlib.h> #include<time.h> #include<math.h> #define CHECK 1000000000
// Structures // A vertex typedef struct vertex{ struct vertex *up; struct vertex *down; struct vertex *left; struct vertex *right; int line, routeNum; // line number and route number } vertex;
// A bar typedef struct bar{ struct vertex *left; struct vertex *right; struct vertex *activeBar; struct bar *next; struct bar *prev; } bar;
// // Global variables // int perm[20]; int n; vertex *upper; // The upper endpoints of lines vertex *lower; // The lower endpoints of lines int *startLines; vertex *activeBar = NULL; // Current active bar double temp;
// Stack of bars bar *head = NULL; bar *tail = NULL;
double count = 0;
int withPrint = 0;
// // Prototypes // inline void init(); void simplePrint();
inline void makeRoot(); void findAllChildren(int); void leftswap(vertex*, vertex*); void rightswap(vertex*, vertex*); int isLeftswappable(vertex*, vertex*); int isRightswappable(vertex*, vertex*);
inline void insertBar(vertex*, vertex*, vertex*, vertex*, vertex*, vertex*);
inline void push(bar*); inline bar* pop();
void print();
/* Main routine / int main(int argc, char argv[]) { int i; clock_t time[2];
if (*argv[1] == ‘p’) {
withPrint = 1; n = argc - 2; printf(“withPrint = 1\n”); printf(“n=%d\n”,n); for (i=1; i<=n; i++) { perm[i] = atoi(argv[i+1]); }
} else {
withPrint = 0; n = argc - 1;
printf(“n = %d\n”,n);
for (i=1; i<=n; i++) { perm[i] = atoi(argv[i]); } }
printf(“\nThe input permutation:\n”); for (i=1; i<=n; i++) { printf(“%d “, perm[i]); } printf(“\n”);
time[0] = clock(); init(); makeRoot(); count++; findAllChildren(1); time[1] = clock();
//count = 2000000000; //count = count * 3; //count = count * 1000; //count++; //count = count + 5555; //count = count - 4400; //count = count * 2;
printf(“Count = %.0f\n”, count); printf(“Time to enumerate: %.2f sec\n”, (double)(time[1]-time[0])/CLOCKS_PER_SEC); }
/* Initialize above[], below[], startLines[]. */ void init() { int i;
upper = (vertex*)malloc(sizeof(vertex[n+1])); lower = (vertex*)malloc(sizeof(vertex[n+1]));
// An error ? for (i=n; i>=1; i–) { upper[i].down = &lower[i]; upper[i].up = upper[i].left = upper[i].right = NULL; upper[i].line = i; upper[i].routeNum = 0; lower[i].up = &upper[i]; lower[i].down = lower[i].left = lower[i].right = NULL; lower[i].line = i; lower[i].routeNum = 0; }
startLines = (int*)malloc(sizeof(int[n+1])); }
/* Simple print method */ void simplePrint() { int i; vertex *curr;
for (i=n; i>=1; i–) { curr = &upper[i]; printf(“%d: “,i); while (curr != NULL) { printf(“%d “,curr->line); curr = curr->down; } printf(“\n”); } printf(“\n”); }
/* Construct root amida */ void makeRoot() { int currNum; // current number int startLine = 1, restartLine; int i, diff; vertex *currVertex, *upperVertex, *lowerVertex; vertex *leftNewVertex, *rightNewVertex;
for (currNum=n; currNum >= 1; currNum–) {
// Calc of the zigzag-path for currNum. while (perm[startLine] != currNum) startLine++; //printf(“startLine = %d, “,startLine);
// Construct startLines[] startLines[currNum] = startLine;
// Move to down currVertex = &upper[startLine]; restartLine = startLine; while (currVertex->down != NULL) { if (currVertex->left != NULL) { currVertex = currVertex->left; restartLine–; } else { currVertex = currVertex->down; } }
// Make zigzag-path for currNum. // We insert a new vertex between upperVertex and lowerVertex. upperVertex = currVertex->up; lowerVertex = currVertex;
for (i = restartLine; i < currNum; i++) { leftNewVertex = (vertex*)malloc(sizeof(vertex)); rightNewVertex = (vertex*)malloc(sizeof(vertex));
leftNewVertex->line = i; leftNewVertex->routeNum = currNum; rightNewVertex->line = i+1; rightNewVertex->routeNum = currNum;
insertBar(upperVertex, lowerVertex, lower[i+1].up, &lower[i+1], leftNewVertex, rightNewVertex);
// Update of upperVertex and lowerVertex. upperVertex = rightNewVertex; lowerVertex = &lower[i+1]; }
startLine = 1; printf(“\n”); }
printf(“\n\n”); }
void insertBar(vertex *upperleft, vertex *lowerleft, vertex *upperright, vertex *lowerright, vertex *leftend, vertex *rightend) { upperleft->down = leftend; lowerleft->up = leftend;
upperright->down = rightend; lowerright->up = rightend;
leftend->up = upperleft; leftend->left = NULL; leftend->down = lowerleft; leftend->right = rightend;
rightend->up = upperright; rightend->left = leftend; rightend->down = lowerright; rightend->right = NULL; }
/* Find all children */ void findAllChildren(int cleanLevel) { vertex *x,*y, *currVertex, *upperleft, *lowerleft; int i, state, route, currCleanLevel = cleanLevel; bar b, *b2;
// Omit for efficiency @ 8th.Apr.2009. if (withPrint == 1) { printf(“%d-th amida, cleanLv = %d:\n”,count,cleanLevel); print(); // Count & Print }
// Turn bar children for (i=n; i>=currCleanLevel-1; i–) { // find turn bar for route of i. // state = 0: go to lowerleft // state = 1: stop state
// If cleanLv = 1 then, we have error case: i = 0!. if (i==0) continue;
currVertex = &upper[startLines[i]]; state = 0; // 0: Go to lower-left, 1: stop(find turn bar)
while (state != 1) { currVertex = currVertex->down; if (currVertex->left != NULL) { currVertex = currVertex->left; } else state = 1; } if (currVertex->right == NULL) { continue; } // We have just found the turn bar of route i.
while (currVertex->line != i) {
lowerleft = currVertex->down; // Find lower-left vertex of current vertex
if (lowerleft->right == NULL) { currVertex = currVertex->right; currVertex = currVertex->down; continue; // increment & continue (skip recursive call)
} else if ( isRightswappable(lowerleft, lowerleft->right) ) {
if (i == cleanLevel-1) {
if (lowerleft->line + 2 < activeBar->line ) ; //break; else{
route = currVertex->routeNum; b.left = lowerleft; b.right = lowerleft->right; b.next = b.prev = NULL; b.activeBar = activeBar; push(&b);
rightswap(lowerleft,lowerleft->right);
activeBar = lowerleft; // Update of active bar count++; // Count up
// Written in 9th.Apr.2009 temp = fmod(count, CHECK); if (temp == 0) { printf(“The %.0f-th amida was generated\n”,count); }
// Recursive call findAllChildren(route + 1);
b2 = pop(); leftswap(b2->left,b2->right); // Return to the parent activeBar = b2->activeBar; // Return to the parent }
} else { // Case of i >= cleanLevel-1
route = currVertex->routeNum; b.left = lowerleft; b.right = lowerleft->right; b.next = b.prev = NULL; b.activeBar = activeBar; push(&b);
rightswap(lowerleft,lowerleft->right);
activeBar = lowerleft; // Update of active bar count++; // Count up
// Recursive call findAllChildren(route + 1);
b2 = pop(); leftswap(b2->left,b2->right); // Return to the parent activeBar = b2->activeBar; // Return to the parent } }
// increment currVertex currVertex = currVertex->right; currVertex = currVertex->down; } // while
} // for loop (biggest loop in this subroutine.)
}
/* rightswap and leftswap */ void rightswap(vertex *left, vertex *right) { vertex *a,*b,*c,*d,*e,*f,*g,*h;
a = left->up; c = right->up; b = c->up; d = c->right;
e = left->down; f = right->down; g = b->up; h = d->up;
// Remove left and right. e->up = a; a->down = e; f->up = c; c->down = f;
// Add left and right to new places. b->up = left; left->down = b; left->up = g; g->down = left;
d->up = right; right->down = d; right->up = h; h->down = right;
left->line = left->line + 1; right->line = right->line + 1; }
void leftswap(vertex *left, vertex *right) { vertex *a,*b,*c,*d,*e,*f,*g,*h;
e = left->up; f = right->up;
b = left->down; a = b->left;
c = b->down; d = right->down;
g = a->down; h = c->down;
// remove left and right e->down = b; b->up = e; f->down = d; d->up = f;
// add left and right c->down = right; right->up = c; right->down = h; h->up = right;
a->down = left; left->up = a; left->down = g; g->up = left;
left->line = left->line - 1; right->line = right->line - 1; }
/* isRightswappable and is Leftswappable */ int isRightswappable(vertex *left, vertex *right) { vertex *leftup = left->up; vertex *rightup = right->up;
if (leftup->up == NULL) return 0; else if (right->up == NULL) return 0; else if ( (leftup->left == NULL) && (rightup->left == NULL) && ( leftup->right == rightup->up )) return 1; else return 0; }
int isLeftswappable(vertex *left, vertex *right) { vertex *leftdown = left->down; vertex *rightdown = right->down;
if (leftdown->down == NULL) return 0; else if (rightdown->down == NULL) return 0; else if ( (leftdown->right == NULL) && (rightdown->right == NULL) && ( leftdown->down == rightdown->left ) ) return 1; else return 0; }
/* Operations for Stack */ void push(bar *b) { if ( (head == NULL) && (tail == NULL) ) { head = tail = b; b->next = NULL; b->prev = NULL; } else if (head == tail) { head = b; b->next = tail; tail->prev = b; } else { head->prev = b; b->next = head; b->prev = NULL; head = b; } }
bar* pop() { bar *temp;
if ( (head == NULL) && (tail == NULL) ) { return NULL; } else if (head == tail) { temp = head; head = tail = NULL; return temp; } else { temp = head; head = head->next; head->prev = NULL; return temp; } }
/* Print amidas */ void print() { vertex **current; int i,j; int wasPrinted[n+1]; // 0: not printed in the previous loop. // 1: surely printed in the previous loop. int final = 0;
current = (vertex**)malloc(sizeof(vertex*[n+1]));
// Initialization for (i=1; i<=n; i++) { current[i] = &upper[i]; wasPrinted[i] = 1; }
while (final != n) {
final = 0;
// 1st: Go down phase. for (i=1; i<=n; i++) { if (wasPrinted[i]==1) { if (current[i]->down != NULL) { current[i] = current[i]->down; } else { final++; } wasPrinted[i] = 0; } }
// 2nd: Print phase. for (i=1; i<=n-1; i++) { printf(“|”); if ( current[i]->right == current[i+1] ) { printf(“-“); wasPrinted[i] = 1; wasPrinted[i+1] = 1; }else { printf(” “); } } printf(“|\n”);
// 3rd: Check final or not. for (i=1; i<=n; i++) { if (current[i] == &lower[i]) { final++; } }
}
printf(“\n”);
}