CODEWITHSUNDEEP
algorithmmath
Daniel Oscar
Daniel Oscar

Reputation: 297

Turning a Matrix into a Vector

This might be more of a mathematical question, but it's for use in a code.

Suppose you have a N x N grid, or matrix. If you wanted to somehow "stretch it", turning it into an array of sorts, such that now every element is to the right or left of each other, like in a vector. But you would like to keep referring to each element by their original reference -- that is row and col. What you would do is divide it's index in the vector by N. It's row would be index//N and column, index % N.

My question is: what if the grid were N x M, resulting in an array of size N*M, how would you get the corresponding position of each element in the grid?

Upvotes: 2

Views: 2076

Answers (3)

SomeDude
SomeDude

Reputation: 14238

I assume by "stretch" you mean you lay the rows next to each other to form a 1-d vector as in

for a 3x4 matrix

a00 a01 a02 a03
a10 a11 a12 a13
a20 a21 a22 a23

you stretch it into 1-d vector like:

a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23

Now given k an index in the above vector, how will you get its corresponding (i,j) in the N x M grid ?

You get them by

i = k / M

j = k - i*M

where M is number of columns

You can check :

for k = 7 (a13) => i = 7/4 = 1 and j = 7 - (1*4) = 3 => (1,3)

for k = 1 (a01) => i = 1/4 = 0 and j = 1 - 0*4 = 1 => (0,1)

for k = 9 (a21) => i = 9/4 = 2 and j = 9 - 2*4 = 1 => (2,1)

An example code in Java is like below:

private static void printPositions(int N, int M) {
    int count = 0;
    for ( int k = 0; k < N*M; k++ ) {
      int i = k/M;
      int j = k - i*M;
      System.out.print( "(" + i + ", " + j + ")" + " " );
      count++;
      if ( count == M ) {
        System.out.println();
        count = 0;
      }
    }
  }

And output for different values of N and M is:

printPositions(3, 4) : 
(0, 0) (0, 1) (0, 2) (0, 3) 
(1, 0) (1, 1) (1, 2) (1, 3) 
(2, 0) (2, 1) (2, 2) (2, 3) 

printPositions(4, 6) : 
(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) 
(1, 0) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) 
(2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) 
(3, 0) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5)

printPositions(1, 5) :
(0, 0) (0, 1) (0, 2) (0, 3) (0, 4)

Upvotes: 1

Daniel
Daniel

Reputation: 7714

Just define a mapping function, that takes a position in a NxM matrix and convert it to a position in the vector:

MATRIX           CORRESPONDING VECTOR

  | 0 1
--|------            0 1 2 3 4 5
0 | 7 2             -------------
1 | 1 9       =>     7 2 1 9 5 6
2 | 5 6

The mapping function can be f(x, y) = y * N + x.

Example 1
        element 1 (position x = 0, y = 1)
        f(0, 1) = y * N + x = 1 * 2 + 0 = 2.
        1 should be in position 2 of the vector

Example 2
        element 6 (position x = 1, y = 2)
        f(0, 1) = y * N + x = 2 * 2 + 1 = 5.
        6 should be in position 5 of the vector

Upvotes: 0

orlp
orlp

Reputation: 117691

This "stretching" is called flattening. This is almost always done in row-major or column-major order. Row-major is also known as C style where column-major is known as Fortran style.

enter image description here

Assuming you use row-major order to flatten a M x N matrix where M is the number of rows and N the number of columns the correct conversion expressions for row-major order are:

col = i % N
row = i / N
-----------
i = row*N + col

For column major order they are:

col = i / M
row = i % M
-----------
i = col*M + row

Both are assuming zero-based indexing for i, col and row, as well as truncating division.

Upvotes: 3

Related Questions