Programming Praxis

Home | Pages | Archives

Matrix Transpose

March 20, 2015 9:00 AM

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.

Share this:

Posted by programmingpraxis

Categories: Exercises

Tags:

5 Responses to “Matrix Transpose”

  1. 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

    By Rutger on March 20, 2015 at 10:09 AM

  2. 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)

    By matthew on March 20, 2015 at 1:24 PM

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

    By matthew on March 20, 2015 at 4:45 PM

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

    By matthew on March 20, 2015 at 4:50 PM

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

    By matthew on March 21, 2015 at 9:00 AM

Leave a Reply

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.