Analysing The Code

This page analyses v2.0 of the solid partitions code that was used to enumerate the numbers of solid partitions. The page was made public on Apr. 13, 2012. The code may be downloaded from here.

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.

//
// 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
  }
}

The full program

#include <cstdio>
#include <iostream>
#include <cstring>
 
// THIS IS VERSION 2.0 OF THE PROGRAM TO COUNT NUMBERS OF TOPOLOGICAL SEQUENCES OF A GIVEN INDEX
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii, int> piii;
 
const int MAX = 100;
 
// a[i] = number of 1-d partitions of sum i //
ll a[MAX+1];
void calculate_1d(int n) {
  for(int i=0; i<=n; i++) a[i]=1;
  for(int k=2; k<=n; k++)
    for(int i=k; i<=n; i++)
      a[i] += a[i-k];
}
 
/************** GENERATING TOPOLOGICAL SEQUENCES *****************/
ll d[MAX+1];            // d[i] = no of topological sequences of index i
int cc[MAX+1][MAX+1];   // no. of columns in given plane,row
int pp, n;              // no. of planes and n
piii x[MAX+1]; int k;   // the sequence of positions and its depth
int curidx;
 
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;
}
 
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 current index (curidx) by (k-1)
}
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 current index (curidx) by (k-1)
}
  cc[p][y]--;
  k--;
}
 
void printconfig() { for(int i=1; i<=k; i++) printf("(%d,%d,%d)  ", x[i].first.first, x[i].first.second, x[i].second); printf("%d\n", curidx+k); }
 
// count the current config and make ur next move
void gen() {
  if(curidx + k > n) return;
  //printconfig();
  if(x[k].first!=pii(1,1)) d[curidx+k]++;
  int p, r, c, t;
  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();
                                exclude(p, r, c);
      }
      if(cc[p][r] == 0) break;
    }
    if(cc[p][1] == 0) break;
  }
}
 
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();
}
//////////////////////////////////////////////
// assumes generate_topological_sequences() and calculate_1d() have been called
ll c[MAX+1];
void calculate_3d_correct(int n) {
  memset(c, 0, sizeof(c));
  for(int i=1; i<=n; i++) {
    for(int j=0; j<=i; j++) c[i] += (a[j]*d[i-j]);
  }
}
 
int main() {
  printf("Enter N: ");
  int N; scanf("%d", &N);
  generate_topological_sequences(N);
  calculate_1d(N);
  calculate_3d_correct(N);
  printf("d[i] = no. of topological sequences of index i\n");
  for(int i=0; i<=N; i++) printf("d[%d] = %lld\n", i, d[i]);
  printf("c[i] = no. of 3d partitions of i\n");
  for(int i=1; i<=N; i++) printf("c[%d] = %lld\n", i, c[i]);
}

Page maintained by Suresh Govindarajan

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License