Convert lower-left matrix triangle 1D index to row, column

Question

How can I convert a 1D index in the lower-left triangle of a grid into a row and column?

For example, consider this table of 1D indices, indexed by row and column

        //       0  1  2  3 4
        //    +--------------- ...
        // 0  |  0
        // 1  |  1  2
        // 2  |  3  4  5
        // 3  |  6  7  8  9 
        // 4  | 10 11 12 13 14
        // ...

Computing the 1D index from row and column is easy.

Computing the column from the row and 1D index would also be easy. The triangle above a row has -- with 0-based indices -- (row^2 + row)/2 indices.

How can I compute the row from the 1D index quickly, ideally in constant time, without any pre-computed mapping?

Answer 1

The $r$ first rows include $T_r=\dfrac{r(r+1)}2$ elements and the linear index corresponding to $(r,c)$, with $0\le c\le r$, is $i:=T_r+c$.

The $T_r$ are called the triangular numbers.

---

Retrieving the row and column from the linear index is a little more tricky.

For given $i$, we have

$$\frac{r(r+1)}2\le i\le\frac{r(r+1)}2+r$$

or, multiplying by 2 then adding 1/4:

$$\left(r+\frac12\right)^2\le 2i+\frac14\le \left(r+\frac32\right)^2-2$$ and this is solved by

$$r=\left\lfloor\sqrt{2i+\frac14}-\frac12\right\rfloor.$$ $c$ follows.

Answer 2

I think this is a solution. Works better with 1-based indices.

        //       1  2  3  4  5
        //    +--------------- ...
        // 1  |  1
        // 2  |  2  3
        // 3  |  4  5  6
        // 4  |  7  8  9 10 
        // 5  | 11 12 13 14 15
        // ...

Let i be the 1D index. Then we have i < (row^2 + row / 2). And for the rightmost value in a row, we have i = (row^2 + row / 2).

That gives the quadratic equation 0 = row^2 + row - 2i. Given i, we can solve for row, using:

q = -1/2 * (b + sgn(b) * sqrt( b^2 - 4ac ))
x1 = q/a    
x2 = c/q

Then:

row = ceil( x2 ) = ceil( c / q )

For example, consider i=10, in the fourth row above. Then:

c = -2 * 10 = -20

q = -1/2 * (1 + 1*sqrt(1 - 4 * 1 * (-2*10)))
  = -1/2 * (1 + sqrt( 1 + 80 ))
  = -1/2 * (1 + 9)
  = -5

row = ceil( c / q ) = -20 / -5 = 4

Doing the same for i=15 results in row = -30/-6 = 5.

The ceiling of the results for anything between 10 < i <= 15 is also 5.