[SOLVED] Map 1D Array to 2D Triangular matrix
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]
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...
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...
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,
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement