Matrix Transpose
March 20, 2015
There is a simple and quick algorithm based on sorting:
1) Make a pass through the input, prepending the row number and column number to each field. Output is a three-tuple of row, column, value for each cell in the matrix. Write the output to a temporary file.
2) Sort the temporary file by column, then row.
3) Make a pass through the sorted temporary file, reconstructing the transposed matrix.
Here’s the code:
$ echo '11 12 13 14
> 21 22 23 24
> 31 32 33 34' |
> awk '{ for (i=1; i sort -n |
> awk ' NR>1 && $2==1 { print "" }; { printf "%s ", $3 }; END { print "" }'
11 21 31
12 22 32
13 23 33
14 24 34
A little three-line shell script is all you need to do the transpose. It’s nice to write programs when someone else has already done the hard work. You can run the program at http://ideone.com/JGTbex.
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])