## Matrix Transpose

### March 20, 2015

Transposing a matrix turns rows into columns and columns into rows; for instance the transpose of the matrix below left is the matrix below right:

11 12 13 14 11 21 31

21 22 23 24 12 22 32

31 32 33 34 13 23 33

14 24 34

That’s easy enough to do when everything fits in memory, but when the matrix is stored in a file and is too big to fit in memory, things get rather harder.

Your task is to write a program that transposes a matrix to large to fit in memory. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

In Python, assuming that we cán fit one row in memory..

If it’s a square matrix with the row and column lengths 2^n, we can transpose in just n linear scans through the array, zipping together the front and back halves (like a riffle shuffle):

zipl (a:s) (b:t) = a:b:zipl s t

zipl _ _ = []

trans 0 m s = s

trans n m s = trans (n-1) m (zipl (take m s) (drop m s))

test n = trans n (2^(2*n-1)) [0..2^(2*n)]

main = print (test 2)

Actually, this will work for any matrix where the number of rows is a power of two. Tidying up the previous solution (now trans m n s expects m to be half the total array size, n is the number of rows, s is the array):

zipl (a:s) (b:t) = a:b:zipl s t

zipl _ _ = []

trans m 1 s = s

trans m n s = trans m (n `div` 2) (zipl (take m s) (drop m s))

main =

print [0..23] >>

print (trans 12 8 [0..23]) >>

print (trans 12 4 [0..23])

Just trying to get some nicer formatting:

And where the number of columns is 2^n, we can invert the process – output all even elements, then all odd elements, repeat n times. In Haskell:

Or maybe this corresponds better to how we might do it with files: