Understanding how v2.0 of the code is the most important part. In particular, I would like to see how dancing links can be incorporated into this version. Once this is done, porting it to v3.2 should be easy. So I have done my best to analyse and explain the code to the best of my ability. I understand the math fully but can't say the same about the code!

## Analysing v2.0 of the code

### The variables

- The variable $k$ stands for the depth.
- The variable $x[m]$ stores the element $x_m =(i,j,k)$ of the sequence $\mathbf{X}=\big\{x[1],x[2],\ldots,x[k]\big\}$ at depth $k$
- The variable $curidx$ stores the current index of a sequence i.e., ignoring the fact that the last element is interesting. Thus, the true index is obtained by adding the current depth $k$ to the $curidx$..
- The most interesting variable is the array $cc[p][r]$ — it is an $N\times N$ array that stores the height (of a skyscraper) at location $(p,r)$. Suppose, $cc[p,r]=3$, then it implies that $(p,r,1)$, $(p,r,2)$ and $(p,r,3)$ must belong to the current sequence else condition 1 (in the def. of a topological sequence) will be violated. Thus, the program always adds a new element at $(p,r,cc[p,r]+1)$.
- $d[m]$ is the number of topological sequences with $index=m$. The program's goal is to compute these numbers for all values of $index \leq N$.
- $N$ is the number that is specified as input to the program and determines the maximum value of the index for which we wish to enumerate the number of topological sequences.

### The routines

Recall the definition of a topological sequence. We being with $P$ being the set of lattice points in the positive octant of three-dimensional space. A sequence $\mathbf{X}= (x_1,x_2,\ldots,x_m)$ containing elements of $P$ is called a **topological sequence** if

- For $1\leq j \leq m$ and $x \in P$, $x \prec x_i$ implies $x = x_i$ for some $i < j$;
- If $m > 0$, there exists $x \in P$ such that $x < x_m$ and $x \neq x_i$, for $1 < i \leq m$.

**Definition:** Let us call a sequence that satisfies condition 1 (but not necessarily condition 2) as an **almost topological sequence**. The reason for creating this definition is because such sequences do occur as sub-sequences of topological sequences.

The sub-routine *possible(x.y,z)* checks whether $(x,y,z)$ can be added to an existing sequence such that **condition 1** is not violated. (Thus it checks to see whether the sequence is almost topological — see definition above) Nearby elements located at $(x-1,y,z)$ and $(x,y-1,z)$ — if they are not filled then it is not allowed. Consider the sequence $\big\{(111)(121)(131)\big\}$ to which we try to add $(1,2,2)$. Since $(1,1,2)$ is not part of the sequence it is not allowed. However, $(1,4,1)$ and $(2,1,1)$ are allowed. **Condition 2** implies that the last element of a topological sequence cannot be of the form $(1,1,z)$ — this is not checked for by *possible(x.y,z)* but such a sequence is not included in the counting of topological sequences — see the second line of the sub-routine *gen()*. However, we do need to consider the sequence which adds $(1,1,2)$ to our sample sequence as it can be part of other topological sequences of longer length.

// // CHECKS FOR CONDITION 1 IN THE DEFINITION OF A TOP. SEQUENCE // That is whether a sequence is almost topological. // bool possible(int x, int y, int z) { if(x>1 && cc[x-1][y] < z) return 0; if(y>1 && cc[x][y-1] < z) return 0; return 1; }

We next analyse the sub-routine *include(p,r,z)*. This routine adds extends an existing sequence if it is permitted by the routine *possible(p,r,c)*. Further, if the position is interesting it increments the current index of the new sequence to reflect this. It thus increases the depth $k$ by one.

void include(int p, int y, int z) { k++; cc[p][y] = z; x[k] = make_pair(pii(p,y), z); if(x[k-1] > x[k]) curidx += (k-1); // if x[k-1] becomes interesting on adding x[k], then increment curidx by (k-1) }

We next analyse the sub-routine *exclude(p,r,z)*. This does the opposite of the sub-routine *include(p,r,z)* — it removes the element $(p,r,z)$ from an existing sequence (thus reducing the depth $k$ by one) along with decrementing the current index, if necessary.

void exclude(int p, int y, int z) { if(x[k-1] > x[k]) curidx -= (k-1); // if x[k-1] is interesting, removal of x[k] needs us to decrement curidx by (k-1) } cc[p][y]--; k--; }

The sub-routine *generate_topological_sequences(N)* initializes the entries at depth 1 and then calls the main routine *gen()* that we will study next.

void generate_topological_sequences(int nn) { memset(cc, 0, sizeof(cc)); memset(d, 0, sizeof(d)); d[0] = 1; k=1; x[1] = make_pair(pii(1,1),1); cc[1][1] = 1; curidx = 0; n = nn; gen(); }

The recursive sub-routine *gen()* is the most important part of the code. Let $N$ denote the maximum index of interest. At every instance that it is called, the system is in state $\mathbf{X}=\big\{x[1],x[2],\ldots,x[k]\big\}$ at depth $k$ and current index $curidx$. Unless, $x[k]$ is of the form $(1,1,z)$, this sequence will contribute a topological sequence of $index=curidx+depth$. Thus, we first increment $d[index]$ by one. We next scan through the $N\times N$ square trying to increase the depth by one by adding a new element, $x[k+1]=(p,r,cc[p,r])$ to the existing sequence if it is possible. When, an element is permitted to be added, we call gen() again to go further down the tree till we reach a topological sequence of $index = N$ at which instance, we no longer go further down the tree and go back a depth to continue the scan through the $N\times N$ square.

// // First consider the current sequence and its contribution to d(index) and then go one deeper in the tree. // void gen() { if(curidx + k > N) return; // if the index of a sequence exceeds the target index N, proceed no further. //printconfig(); if(x[k].first!=pii(1,1)) d[curidx+k]++; // increase the count of of d[index=curidx+k] by one except when cond. 2 clicks int p, r, c, t; // // Start the scan through the NxN square // for(p=1; p<=N; p++) { for(r=1; r<=N; r++) { c = cc[p][r]+1; if(possible(p, r, c)) { include(p, r, c); gen(); // recursively go down the tree until the required index is reached. exclude(p, r, c); } if(cc[p][r] == 0) break; // one cannot add any more beyond this value of r (for fixed p) -- makes the code run faster } if(cc[p][1] == 0) break; // one cannot add any more beyond this value of p -- makes the code run faster } }