🔒 Locked

[SOLVED] Map 1D Array to 2D Triangular matrix

Started by Chire Mar 20, 2010 at 12:32 PM 2 replies 4.8k views

Original Post

Mar 20, 2010 at 12:32 PM

hello, im running with a little problem on an algorithm lets say i have this array of size N(N+1)/2, where N is the size of the 2D matrix that represents it, in this case N=5: A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]. i need to map it to a 2D triangular matrix: A[5][5] = 0..1..2...3...4 -..5..6...7...8 -..-..9...10..11 -..-..-...12..13 -..-..-....-..14 so, what im trying to do is an algorithm that receives as parameter a given index x= 0..14, and returns i,j of the matrix. for example. function(0) returns i=0, j=0. function(7) returns i=1, j=3. function(11) return i=2, j=4. function(14) returns i=4, j=4. i have came up with different algorithms, one worked for 3x3 Matrixes, but i cannot figure out the generic ecuation for any square triangle matrix. any help is welcome, meanwhile i will keep trying. EDIT: From my análisis, the key is to calculate "i", since j can be calculated very easy after that. [Edited by - Chire on March 20, 2010 6:05:51 PM]

Emergent

Mar 20, 2010 at 1:24 PM

Hmmm....

The obvious brute-force way would be to start with x, and then subtract off n, then n-1, then n-2, etc, until you can't subtract off any more; the number of subtractions is 'i;' 'j' is 'i' plus whatever is left.

It'd be nice to turn this into a mod/divide though, but this isn't jumping out at me...

The other direction -- "given i,j, return x" -- is easy enough though; you get a quadratic form...

Chire

Mar 20, 2010 at 1:37 PM

Quote:
Original post by Emergent
Hmmm....

The obvious brute-force way would be to start with x, and then subtract off n, then n-1, then n-2, etc, until you can't subtract off any more; the number of subtractions is 'i;' 'j' is 'i' plus whatever is left.

It'd be nice to turn this into a mod/divide though, but this isn't jumping out at me...

The other direction -- "given i,j, return x" -- is easy enough though; you get a quadratic form...

yea, brute force works good for small sizes.

there must be an expression to calculate "i", lets hope.
i will post any advance i get. and any help is welcome,

Chire

Mar 20, 2010 at 2:03 PM

ok friends
i got the expression mathematical 100%.
this will help you optimize a lot of memory usage when matrix calculations only operate on the triángular part, like in my case.
i will go step by step.

1) view A as the representation of lower triangular part (totally equivalent)
A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
A[5][5] =
0...-...-...-...-
1...2...-...-...-
3...4...5...-...-
6...7...8...9...-
10..11..12..13.14

2) now:

given c = 0..14, we know that there will be a sumatory of n, n times until c is reached. Sumatory(i) when i =0..n can be written as
n(n+1)/2 and this is equal c.
c=n(n+1)/2
which is the same as n^2 + n - 2c = 0.

3) then, what you need to program is this n Value
n = (-b + sqrt(b^2 - 4a*2c))/2a ==> simplier n = (-1+sqrt(1 + 4*2c))/2

4)finally calculate i and j
i = truncate(n).
j = c - i*(i+1)/2

:)

[Edited by - Chire on March 20, 2010 5:03:58 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.