CODEWITHSUNDEEP
calgorithmmatrixtranspose
user3746892
user3746892

Reputation: 67

Transpose a Matrix which is written as a single vector?

I'm mainly just looking for some ideas on how to do this, not looking for specific code or anything like that.

I'm writing a C program in which the user inputs an n by n matrix and this matrix is stored as one long vector. For example if the matrix was: {{0,1},{2,3}} it would be stored as such:

int *a;
a = {0,1,2,3};

Does anyone have any ideas on how I can go about transposing this matrix to make it:

a = {0,2,1,3}

Obviously, this is easy in the case of a 2 by 2 matrix, but I'm having a bit of trouble generalizing when it comes to the case of an n by n matrix.

My first thought was to just loop through the array and first take out all the elements which are indices kn + 0 for 0 <= k <= n, and then do the same for kn + 1, then k*n + 2, and so on but this doesn't seem to be a valid strategy since I don't know the value of n?

Edit: To clarify, the matrix is an n by n matrix, and one of the other inputs is the value of n. What I meant was that since I don't have a constant value for n, as the user inputs it, I was having trouble coming up with an algorithm.

Upvotes: 1

Views: 761

Answers (2)

jamesqf
jamesqf

Reputation: 215

Since you know n, any element can be addressed as a [j * n + i], where i and j are column & row.

Upvotes: 4

Ryan J
Ryan J

Reputation: 8323

Since what was asked for was some ideas and not just code, I thought I'd throw in some general advice to help derive an answer.

First, if the input is an NxN matrix stored as a 1D array, then you will need to know the value of N in order to solve the problem. Your comment about not knowing N means that your function will have to accept that value.

The basic idea is to loop through all the elements in the array, swapping element (i,j) with (j,i).

If you think about it in terms of how to find the element at (i,j), the problem becomes simpler to solve. If the matrix is of size NxN, that means, in your input array, for every N values (j), the row increases (i). So, coming up with a formula for finding any given element becomes a function of the column number, the row number, and the value of N.

More precisely the index of element (i,j) is, N*i + j, the number of rows times the row number plus the number of columns.

For example, finding the value at (3,2) in a 5x5 matrix would yield an index into a 1D array of 5*3 + 2 = 17

Conceptually you can see that with the following example:

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20 
21 22 23 24 25

As a 1D array:

{ series of integers from 1 - 25 }

If we wanted to see where in this array the element at (3,2) = 18, we'd look for the index of 18 in the 1D array, and see that it's 17.

To transpose the matrix, you'd simply swap with the element at (j,i), in this example (2,3) = 14

A simple algorithm to perform this operation on all elements up to N will get you your result.

HTH, good luck

Upvotes: 2

Related Questions