Derivation of Index Formulae For 1-D, 2-D, 3-D and n-D Array

by

Array is a fundamental data structures in programming language. It is used to store collections of elements of similar type of data type. Elements store in array can be accessed with the help of their index number. And with the help of formulas we can calculate the index number of the given element. The indexing formulas for arrays depend on their dimensions (1-D, 2-D, 3-D, etc.). And it is crucial for accessing and manipulating their elements efficiently. Let’s go through the derivation of index formulas for 1-D, 2-D, 3-D, and n-D arrays.

1-D Array Index Formula

In a 1-D array, elements are stored in a linear fashion. The index formula is straightforward. Each element can be accessed directly by its position in the array.

  • Formula: index = i
  • Explanation:
    • i is the position in the array.
    • If the array starts at index 0 (zero-based indexing), the first element is at index = 0, the second at index = 1, and so on.

Example:

In a 1-D array A[5] = {a, b, c, d, e}, A[2] would directly access the third element, which is c.

2-D Array Index Formula

A 2-D array can be thought of as a matrix or table with rows and columns. It requires two indices to access an elements. One will denote the row and other will denote the column. The index formula for a 2-D array (row-major order) is:

  • Formula: index = (i * column_count) + j
  • Explanation:
    • i is the row index, and j is the column index.
    • column_count is the total number of columns in the array.
    • The formula calculates the starting index of the ith row (i * column_count) and adds the column index to it.

Example:

In a 2-D array B[3][4] (3 rows, 4 columns), the element at the second row and third column (B[1][2]) is accessed. The index is (1 * 4) + 2 = 6.

3-D Array Index Formula

A 3-D array can be visualized as a collection of 2-D matrices. You can also thought a 3-D array is a stack of 2-D arrays (or matrices). This structure is often used in scientific computing and graphics. The index formula for a 3-D array (row-major order) is:

  • Formula: index = (i * plane_size) + (j * row_size) + k
  • Explanation:
    • i, j, and k represent indices along the three dimensions.
    • plane_size is the total number of elements in each 2-D matrix (plane), which is row_count * column_count.
    • row_size is the number of elements in each row (column_count).
    • The formula calculates the start of the ith plane, adds the start of the jth row within that plane, and then adds the kth element within that row.

n-D Array Index Formula

For an n-dimensional array, the index formula generalizes the concept of the 3-D array formula. In n-dimensional array, the indexing becomes more complex as we add more dimensions. Assuming an n-dimensional array C[dim1][dim2]...[dimN] and an index set I[i1][i2]...[iN], the index formula in row-major order is:

  • Formula: index = Σ (ik * Sk) for k = 1 to N
  • Explanation:
    • ik is the index in the k-th dimension.
    • Sk is the size of a single element in the k-th dimension. It is computed as the product of the sizes of all dimensions after k.
    • The formula sums up the products of each index with its corresponding stride (Sk). The stride represents the number of elements to skip over in the current dimension to move to the next element in the next dimension.

For example, in a 4-D array C[10][20][30][40], the index formula involves calculating the stride for each dimension and then using these strides to compute the overall index.