CODEWITHSUNDEEP
arraysalgorithm
Redek
Redek

Reputation: 1420

Getting the Row and Column of a Triangular Matrix, Given the Index

I am working with a MxM triangular matrix which has the following form:

M = [m00 m10 m20 m30 m40]
    [m11 m21 m31 m41    ] 
    [m22 m32 m42        ]
    [m33 m43            ]
    [m44                ]

If it's easier to picture this in terms of indexes, it would look like this:

M = [0 1 3 6 10]  
    [2 4 7 11  ]
    [5 8 12    ]
    [9 13      ]
    [14        ]

I know this way of indexing might look odd but it would be much easier if I could keep the indexing system as it is in order for this module to work well with others.

I am struggling with an algorithm that takes an index and size of the matrix that can return the row and column that the given index falls under. Ideally I would have 2 functions such as these:

int getRow (int index, int size);
int getCol (int index, int size);

So getRow (7, 5) would return 3

And getCol (7, 5) would return 1

I have come across this thread already but I cannot seem to modify the solution given there to work for the way I am indexing.

algorithm for index numbers of triangular matrix coefficients

Upvotes: 9

Views: 2471

Answers (1)

sch
sch

Reputation: 27506

New Answer

You can find the row and column using the following formulas:

int row = floor(-0.5 + sqrt(0.25 + 2 * index));
int triangularNumber = row * (row + 1) / 2;
int column = index - triangularNumber;

This works because the first item in each row is a triangular number (0, 1, 3, 6, 10, 15, ...). So the biggest triangular number that is lower than index gives us the row. Then column is simply the difference between index and that triangular number.

Also, note that you don't need the parameter M.

Old Answer

This code will give you both the row and column of index.

int triangularNumber = 0;
int row = 0;
while (triangularNumber + row < index) {
    row ++;
    triangularNumber += row;
}
int column = index - triangularNumber;

Upvotes: 9

Related Questions