How to map the indexes of a matrix to a 1-dimensional array (C++)?
Solution 1
The way most languages store multi-dimensional arrays is by doing a conversion like the following:
If matrix
has size, n (rows) by m (columns), and we're using "row-major ordering" (where we count along the rows first) then:
matrix[ i ][ j ] = array[ i*m + j ]
.
Here i goes from 0 to (n-1) and j from 0 to (m-1).
So it's just like a number system of base 'm'. Note that the size of the last dimension (here the number of rows) doesn't matter.
For a conceptual understanding, think of a (3x5) matrix with 'i' as the row number, and 'j' as the column number. If you start numbering from i,j = (0,0) --> 0
. For 'row-major' ordering (like this), the layout looks like:
|-------- 5 ---------|
Row ______________________ _ _
0 |0 1 2 3 4 | |
1 |5 6 7 8 9 | 3
2 |10 11 12 13 14| _|_
|______________________|
Column 0 1 2 3 4
As you move along the row (i.e. increase the column number), you just start counting up, so the Array indices are 0,1,2...
. When you get to the second row, you already have 5
entries, so you start with indices 1*5 + 0,1,2...
. On the third row, you have 2*5
entries already, thus the indices are 2*5 + 0,1,2...
.
For higher dimension, this idea generalizes, i.e. for a 3D matrix
L by N by M:
matrix[ i ][ j ][ k ] = array[ i*(N*M) + j*M + k ]
and so on.
For a really good explanation, see: http://www.cplusplus.com/doc/tutorial/arrays/; or for some more technical aspects: http://en.wikipedia.org/wiki/Row-major_order
Solution 2
For row-major ordering, I believe the statement matrix[ i ][ j ] = array[ i*n + j ]
is wrong.
The offset should be offset = (row * NUMCOLS) + column
.
Your statement results to be row * NUMROWS + column
, which is wrong.
The links you provided give a correct explanation.
Solution 3
Something like this?
//columns = amount of columns, x = column, y = row
var calculateIndex = function(columns, x, y){
return y * columns + x;
};
The example below converts an index back to x and y coordinates.
//i = index, x = amount of columns, y = amount of rows
var calculateCoordinates = function(index, columns, rows){
//for each row
for(var i=0; i<rows; i++){
//check if the index parameter is in the row
if(index < (columns * i) + columns && index >= columns * i){
//return x, y
return [index - columns * i, i];
}
}
return null;
};
Related videos on Youtube
Fernando Aires Castello
I'm a Java software developer from Florianópolis, SC (Brazil). I can speak Portuguese (natively), English, basic Romanian and basic modern Greek. I am able to program in C/C++, C#, Java, Javascript, Delphi, BASIC and Assembly (especially for Z80 and x86 architectures).
Updated on July 09, 2022Comments
-
Fernando Aires Castello almost 2 years
I have an 8x8 matrix, like this:
char matrix[8][8];
Also, I have an array of 64 elements, like this:
char array[64];
Then I have drawn the matrix as a table, and filled the cells with numbers, each number being incremented from left to right, top to bottom.
If I have, say, indexes 3 (column) and 4 (row) into the matrix, I know that it corresponds to the element at position 35 in the array, as it can be seen in the table that I've drawn. I believe there is some sort of formula to translate the 2 indexes of the matrix into a single index of the array, but I can't figure out what it is.
Any ideas?
-
WhozCraig over 11 years
arr[i*cols+j]
for equivalentmatrix[i][j]
indexing, assuming you want row-major ordering, andcols
is your defined row width in columns (in your example's case,8
). -
Fernando Aires Castello over 11 yearsI've tried all kinds of simple calculations like multiplying row * column * 8, dividing, etc. but it doesn't work. I'm not very good at math.
-
-
Fernando Aires Castello over 11 yearsI can't believe it was so simple... Very informative, thank you.
-
Michael Dorst about 10 yearsAre you responding to zhermes' answer? If so you should probably just edit his/her post with your correction.
-
Stewart_R over 9 yearsPerhaps you could you explain a little of how this relates to (and answers) the OP's original question?
-
Donny Verduijn over 9 yearsI should read a little better. It actually does the exact opposite as what the OP has asked for. This converts 35,8,8 to 3,4.
-
Donny Verduijn over 9 yearsNow it illustrates both conversions :)
-
DilithiumMatrix over 8 yearsI'm pretty sure the current description is correct (as also described by @user1480848's answer below --- and corresponding edit on Mar 4, 2014). Please leave a comment if you don't think so - instead of editing the answer directly.
-
Mohamad over 8 years@DilithiumMatrix shouldn't the formula be
j + (i * n)
and noti + (j * n)
as you suggest? Consider coordinates2,3
, which should return 13 using your matrix:3 + (2 * 5) = 13
. If we used your formula instead, we would get2 + (3 * 5) = 17
. Am I missing something? -
DilithiumMatrix over 8 years@Mohamad absolutely, thanks! That's also what user1480848 described below... I think I must have rolled back to the wrong edit. Should be fixed now. I hope.
-
Nitij over 8 yearsAlthough I had to swap row and columns for my use but this is exactly what I was looking for.
-
TMOTTM over 3 yearsAnd just to be sure because it's not always the same convetion, by 'n' you mean number of rows and 'm' the number of columns, right?
-
DilithiumMatrix over 3 years@TMOTTM, yes that's right. I tried to clarify the answer.
-
arapEST over 2 yearsHe is correct, you are probably setting up the (raw)array column major way in your head :)