52

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?

Fernando Aires Castello
  • 1,203
  • 3
  • 17
  • 23
  • 3
    `arr[i*cols+j]` for equivalent `matrix[i][j]` indexing, assuming you want row-major ordering, and `cols` is your defined row width in columns (in your example's case, `8`). – WhozCraig Dec 23 '12 at 23:39
  • I'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 Dec 23 '12 at 23:40

3 Answers3

108

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

DilithiumMatrix
  • 17,795
  • 22
  • 77
  • 119
  • 3
    I can't believe it was so simple... Very informative, thank you. – Fernando Aires Castello Dec 23 '12 at 23:53
  • I'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. – DilithiumMatrix Nov 04 '15 at 02:51
  • 1
    @DilithiumMatrix shouldn't the formula be `j + (i * n)` and not `i + (j * n)` as you suggest? Consider coordinates `2,3`, which should return 13 using your matrix: `3 + (2 * 5) = 13`. If we used your formula instead, we would get `2 + (3 * 5) = 17`. Am I missing something? – Mohamad Nov 21 '15 at 01:13
  • 1
    @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. – DilithiumMatrix Nov 21 '15 at 15:50
  • And 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? – TMOTTM Sep 29 '20 at 16:07
  • @TMOTTM, yes that's right. I tried to clarify the answer. – DilithiumMatrix Sep 29 '20 at 16:39
13

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.

mvelusce
  • 133
  • 1
  • 5
7

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;
};
Donny Verduijn
  • 424
  • 6
  • 10