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.
Programming Praxis 
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:
pairs (a:b:s) = (a,b):pairs s pairs _ = [] trans 0 s = s trans n s = trans (n-1) (uncurry (++) $ unzip $ pairs s) main = print [0..23] >> print (trans 1 [0..23]) >> print (trans 2 [0..23]) >> print (trans 3 [0..23])Or maybe this corresponds better to how we might do it with files:
evens (a:s) = a : odds s evens _ = [] odds (_:s) = evens s odds _ = [] trans 0 s = s trans n s = trans (n-1) (evens s ++ odds s) main = print [0..23] >> print (trans 1 [0..23]) >> print (trans 2 [0..23]) >> print (trans 3 [0..23])