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.

Posted by programmingpraxis

Filed in Exercises

5 Comments »

5 Responses to “Matrix Transpose”

Rutger said

March 20, 2015 at 10:09 AM

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

file_like_object = []
file_like_object.append([11,12,13,14,11,21,31])
file_like_object.append([21,22,23,24,12,22,32])
file_like_object.append([31,32,33,34,13,23,33])
file_like_object.append([14,24,34])


max_row_length = 1
i = 0
while i < max_row_length:
	for row in file_like_object:
		if len(row) > max_row_length:
			max_row_length = len(row)
		if i < len(row):
			print row[i],
	print
	i += 1

matthew said
March 20, 2015 at 1:24 PM
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)
matthew said
March 20, 2015 at 4:45 PM
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])

matthew said

March 20, 2015 at 4:50 PM

Just trying to get some nicer formatting:

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])

matthew said

March 21, 2015 at 9:00 AM

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])

Programming Praxis