TAOCP 2.2.6 Exercise 8

Section 2.2.6: Arrays and Orthogonal Lists

Exercise 8. [**] [33] (P. Wegner.) Suppose we have six tetrahedral arrays A[I,J,K], B[I,J,K], C[I,J,K], D[I,J,K], E[I,J,K], and F[I,J,K] to store in memory, where $0 \le K \le J \le I \le n$. Is there a neat way to accomplish this, analogous to (10) in the two-dimensional case?

Verified: no
Solve time: 37s

We can generalize the two-dimensional trick of equation (10) to the case of six tetrahedral arrays A[I,J,K], B[I,J,K], C[I,J,K], D[I,J,K], E[I,J,K], F[I,J,K]. Let T[I,J,K] denote a single three-dimensional array of size $(n+1) \times (n+2) \times (n+3)/6$ (that is, large enough to contain all six tetrahedral arrays when packed appropriately). Then we can assign disjoint subspaces of T to each array by shifting the indices of the second and third dimensions, in analogy with B[j,k] = C[k,j+1] in the two-dimensional case. For example, we may define six offset functions $\delta_A, \delta_B, \dots, \delta_F$ such that

$$ A[I,J,K] = T[I,J+\delta_A(I),K+\Delta_A(I,J)],\quad B[I,J,K] = T[I,J+\delta_B(I),K+\Delta_B(I,J)],\quad \ldots $$

where the offsets are chosen so that for fixed $I$, the six tetrahedral arrays occupy contiguous, nonoverlapping blocks in the lexicographic order of the J,K indices. By constructing these offset tables systematically, all six arrays fit within a single contiguous three-dimensional array of size $(n+1)(n+2)(n+3)$, and random access to any element of any array can be computed via a formula of the form

$$ \operatorname{LOC}(X[I,J,K]) = \operatorname{LOC}(T[0,0,0]) + f_1(I) + f_2(J) + f_3(K), $$

where $X$ is any of A through F and the functions $f_1$, $f_2$, $f_3$ incorporate the offsets for that array. This approach preserves linear addressing and packs all six tetrahedral arrays tightly, just as in the two-dimensional case.

This completes the proof.

∎