Analysing the code

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

  1. For $1\leq j \leq m$ and $x \in P$, $x \prec x_i$ implies $x = x_i$ for some $i < j$;
  2. 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.

// 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) {
  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)

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;

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.
  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
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License