matrix transpose

tqt · April 17th, 2009, 4:47 pm

I recently got asked this question during a phone interview:Suppose you have a n x m matrix stored in an one dimensional array in column-major order, that is, element (i,j) in the matrix is at position i+j*n in the one dimensional array. Write an algorithm that transposes the matrix in-place.According to the interviewer, you should do this "without allocating an amount of memory of the same order as the matrix". Is it possible to do this without keeping a tab of which elements we already touched? What I mean is the following:We know element (i,j) in the original matrix (position i+n*j in the array) goes to element (j,i) in the transposed matrix (position j+i*m in the array). In turn, j+i*m is the position of element (k,l) in the original matrix where k=a mod n, and l=(a-k)/n. If one loops over this sequence it'll eventually go back to element (i,j). Without keeping a tab of the elements we already transposed, how do I know which element to proceed with after a cycle is taken care of?My initial approach would be storing a bit array of size n*m and setting each element to 1 after being visited on the scheme above, but this array is clearly "of the same order as the matrix".ps. this is not a problem for square matrices (n x n) since element (i,j) = i+j*n goes to (j,i) = j+i*n, which in turn goes to the original i+j*n. That is, for square matrices this is done easily by swapping each element on the upper triangular with the corresponding element on the lower triangular.

cm27874 · April 20th, 2009, 4:43 am

If running time is not an issue: to check if position i has not been included in a previous cycle, run through its cycle without mapping elements. If you reach a position j<i, position i must have been taken care of already. Otherwise, run through the cycle again, this time mapping elements.

tqt · April 20th, 2009, 12:40 pm

I thought about doing such a dry-run on the cycle to determine whether position i was already swapped or not, but at the the time it seemed quite inefficient.On the other hand, maybe the interviewer wanted exactly that kind of answer. I assumed the question was on optimizing the memory usage without sacrificing too much running time.

lega85 · April 21st, 2009, 7:12 am

Here is the algorithm, which doesn't use much memory. Suppose, you've got numbers 1...m*n. Mark every n number, and send marking numbers to the end of the queue. You should do it in the way that doesn't change the order of marked and unmarked elements, i.e on first step you'll get 1...n-1, n+1,...2n-1,...m*n-1,n,2n,...,mn. You can do it using just swapping of 2 neighbor elements. Then forget about last m elements and do the same thing marking every n-1 element, after that n-2, and so on until 1. After that you'll get transported matrix.Just to illustrate it for matrix 3x4: 1) 1 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 6 7 89 10 11 122) 1 2 3 5 6 7 9 10 11 4 8 123) 1 2 5 6 9 10 3 7 11 4 8 124) 1 5 9 2 6 10 3 7 11 4 8 121 5 92 6 103 7 114 8 12for 4x31)1 2 3 4 5 6 7 8 910 11 122) 1 2 4 5 7 8 10 11 3 6 9 123) 1 4 7 10 2 5 8 11 3 6 9 12 P.S. Sorry for my English.

tqt · April 21st, 2009, 8:08 pm

lega85, that's an interesting idea, but it'll be less efficient than the other method where we do a dry-run to determine if the element was already swapped or not. The problem here is that on each iteration you need to reorder a lot of data in the array. Notably, your method works quite well if there are just a few rows but doesn't perform well if there are a bunch of rows. I wrote some code for the 3 methods, here are some timings:

lega85 · April 23rd, 2009, 10:56 pm

tqt, why did you use in 3rd and 4th cases 1501 instead of 1500? It seems that the dry-run method strongly depends on average cycle length. (without using cycles)-methods uses about O(n*n*m) swaps, and dry-run should use something like O(A*exp(C*(m*n)/A)) where A is average cycle length. For NxN matrices A=2 and i think 3rd algorithm should be the fastest. Timings showed that in your examples A is quite big(timings almost equal C*m*n, so exp didn't make great impact ). So when you used 1501 instead of 1500 i thought that it may be because when GCD(m,n) is big, A is quite small and 2nd algorithm is in trouble (don't even know if it's true and don't want to figure it out) ). Were there any problems with 1500? Just interesting. (Although even in this case we can add fictive rows in order to achieve smaller GCD(m,n)).

tqt · April 24th, 2009, 1:10 pm

Good eye! I ran several timing tests, but pasted only a few in here. Below are some more results with different gcd(n,m) values.

tqt · April 24th, 2009, 2:13 pm

lega85, both cycles approaches use the same number of swaps; every element always get swapped to the right position, so the number of swaps is less or equal than n*m-2. When no extra memory is used you certainly need to follow the cycles (without any swaps) so it would at most be of the order O(n*m*A). I'm not sure where you got the exp term from.This seems more in line with the results; if n is very large and greater than m, the third method will be the worst since n*n*m > n*m*A. If m>n and m is very large then A could also be large (>n), so the 3rd method would perform better.

lega85 · April 24th, 2009, 3:10 pm

You are right, i just misread cm27874's message and thought that for next element we should simulate all previous process without swapping.

vishalshekhar · July 2nd, 2009, 11:21 am

ExSan · July 22nd, 2009, 8:23 pm

Suppose you have a n x m matrix stored in an one dimensional array in column-mayor order that is, element (i,j) in the matrix is at position i+j*n in the one dimensional array. Write an algorithm that transposes the matrix in-place. You should do this without allocating an amount of memory of the same order as the matrix. Roughly the Algorithm Let be the Array V[1, m*n] the vectorial-row representation of matrix A[m*n] Set a Pivot at the beginning, perform m rotations with the n remaining data n times advance the Pivot to the next data, decrease the rotations, repeat till end is reached 1 2 3 4 5 6 7 8 9 MATRIX - VECTORIAL Row REPRESENTATION 1 2 3 4 5 6 7 8 9 Rotate 2 positions 3 times pivot: 2 col-> 2 1 4 5 6 7 8 9 2 3 1 4 7 8 9 2 3 5 6 1 4 7 2 3 5 6 8 9 Rotate 1 positions 3 times pivot: 3 col-> 5 1 4 7 2 5 6 8 9 3 1 4 7 2 5 8 9 3 6 1 4 7 2 5 8 3 6 9 Rotate 0 positions 3 times pivot: 6 col-> 8 TRANSPOSED MATRIX - VECTORIAL Row REPRESENTATION 1 4 7 2 5 8 3 6 9From the Downloadable File extract program Transpose_Matrix to your desktop and execute.

DRead · November 26th, 2009, 1:01 pm

Hey everybody, this is my first post so please tell me if I do something wrong. I had a go at this a little while ago as it seemed like a nice problem but forgot to post what I came up with. I thought people might find it interesting, mostly because if this came up in an interview my code is very short and the method easily learnt. The solution I came up with is at the bottom (working in C, I did it in row rather than column major order but the principle is the same).Here I have just written a simple function "Swap" to switch the elements. m and n represent the number of rows and columns respectively and Array is (unsurprisingly) the name of the 2D array. I think it is not as efficient as the methods already discussed but interesting nonetheless. I am happy to discuss more the details of how it works and how efficient it is but I understand I am dragging up quite an old thread so perhaps no-one cares anymore.Hopefully I have not made a faux pas with this post.

AVt · November 28th, 2009, 7:38 pm

I neither understand the deeper sense of most interview question (beyond the usual nonsense like "want to see how attack problems") nor would be able to answer them ...Here you go:http://en.wikipedia.org/wiki/Transpose# ... tionExcept it was around his Master thesis in CS or a special lecture I seriously doubt the interviewer would have been able to answer that in an examinationThe only reasonable reply quite often would be "why? what do you actually want to do?"

yikelu · January 19th, 2010, 5:43 am

I almost didn't notice this solution in "Background" on the wikipedia article.But this is what I came up with. Label the matrix as transposed and use a different access function. Done - no permutations, no memory allocation, no headache. Most elegant way to solve the problem as stated.