Jump to content
  • Advertisement
Sign in to follow this  
Chire

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

This topic is 3014 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
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...

Share this post


Link to post
Share on other sites
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,


Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!