TAOCP 2.2.6 Exercise 6
For the array `A[i,j,k]` with $0 \le k \le j \le i \le n$, storing the elements in lexicographic order of the indices means that `k` varies fastest, then `j`, then `i`.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 6. ▶ [**] [M24] Consider the "tetrahedral arrays" A[i,j,k], B[i,j,k], where $0 \le k \le j \le i \le n$ in A, and $0 \le i \le j \le k \le n$ in B. Suppose that both of these arrays are stored in consecutive memory locations in lexicographic order of the indices; show that LOC(A[I,J,K]) = a_0 + f_1(I) + f_2(J) + f_3(K) for certain functions $f_1$, $f_2$, $f_3$. Can LOC(B[I,J,K]) be expressed in a similar manner?
Verified: no
Solve time: 36s
For the array A[i,j,k] with $0 \le k \le j \le i \le n$, storing the elements in lexicographic order of the indices means that k varies fastest, then j, then i. The number of elements with fixed i is the sum of the first $i+1$ triangular numbers: for a given i, the number of j,k pairs with $0 \le k \le j \le i$ is $\sum_{j=0}^{i} (j+1) = \frac{(i+1)(i+2)}{2}$. Likewise, for fixed i and j, the number of elements with varying k is j+1. Therefore the location of A[I,J,K] can be written as
$$ \operatorname{LOC}(A[I,J,K]) = \operatorname{LOC}(A[0,0,0]) + \sum_{i'=0}^{I-1} \frac{(i'+1)(i'+2)}{2} + \sum_{j'=0}^{J-1} (j'+1) + K = a_0 + f_1(I) + f_2(J) + f_3(K), $$
where $f_1(I) = \sum_{i'=0}^{I-1} \frac{(i'+1)(i'+2)}{2}$, $f_2(J) = \sum_{j'=0}^{J-1} (j'+1)$, and $f_3(K) = K$, so that the condition of Eq. (8) is satisfied.
For the array B[i,j,k] with $0 \le i \le j \le k \le n$, the lexicographic order requires i varying fastest, then j, then k. In this case, the number of elements for fixed k is $\sum_{j=0}^{k} (j+1) = \frac{(k+1)(k+2)}{2}$, and for fixed k and j, the number of i values is j+1. Hence
$$ \operatorname{LOC}(B[I,J,K]) = \operatorname{LOC}(B[0,0,0]) + \sum_{K'=0}^{K-1} \frac{(K'+1)(K'+2)}{2} + \sum_{J'=0}^{J-1} (J'+1) + I, $$
which is not of the form $a_0 + g_1(I) + g_2(J) + g_3(K)$ with each $g_r$ depending on a single index only, because the outer sum depends on K and includes contributions that involve J. Therefore LOC(B[I,J,K]) cannot, in general, be expressed as a sum of functions of individual indices alone.
This completes the proof.
∎