9

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

Community
  • 1
  • 1
Redek
  • 1,311
  • 1
  • 13
  • 20

1 Answers1

9

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;
sch
  • 27,436
  • 3
  • 68
  • 83
  • Thank you very much! It seems I was trying to figure it out algebraically which was causing me problems but this iterative solution works just as nicely. – Redek Mar 12 '12 at 21:24
  • @Redek, are you sure you want change matrix indexing and find row amd column in O(n)? – Saeed Amiri Mar 12 '12 at 21:29
  • @Saeed Amiri, I would be open to a more efficient solution without a doubt but this solution does work well and for the system which I will be implementing this, the max size of this matrix will only be a few thousand which in my opinion is pretty negligible. That being said, I would certainly welcome other solutions for my own benefit and even for others who are running into a similar problem but cannot afford the O(n) limitation. – Redek Mar 12 '12 at 21:41
  • @sch it is O(n) because matrix is n*n, Also I agree with you because you answered, I can't understand why OP changed alignments to get this runtime! – Saeed Amiri Mar 12 '12 at 21:46
  • @Saeed Amiri, I dont think I follow? How have I changed alignments? I am very happy with sch's solution, both for the explanation given and at how quickly he replied. As ideal as it would be to have the perfect O(1) solution, I do have other parts of the system that depend on this, which in turn does have a deadline so I am happy that I was able to come across a solution. – Redek Mar 12 '12 at 21:55
  • @SaeedAmiri - Finally, it was simple to find the formulas for `row` and `column`. There is only a second degree equation to solve. – sch Mar 12 '12 at 22:14
  • @Redek, when I saw your question, I thought you plan to reduce memory size with efficient access time, but when I saw you are happy just by founding related functions, I thought it is a homework and there isn't any special reason to have such a functions. – Saeed Amiri Mar 12 '12 at 22:41
  • @SaeedAmiri - Ohh no, the initial reason was not for efficiency, I was simply stumped on the problem. And no it's not for homework. – Redek Mar 12 '12 at 23:52