Matrix rotator

John Haugeland stonecypher@REDACTED
Mon Jun 15 08:50:42 CEST 2009


> The goal is to rotate an arbitrary sized input matrix 90 degrees
> counterclockwise, e.g.:

There is a reasonably efficient implementation under the name zip_n in
ScUtil's sc_lists module.  I did not write it, but rather beefed it
from a webpage; there's attribution in the source (can't remember
where it comes from offhand.)  zip_n also happens to vertically flip
the end result during the rotation, which tends to be more
algorithmically useful.

A naive implementation is straightforward, though it has performance
problems.  Fixing the performance problems here is pretty
straightforward, but leads to much less understandable of an answer,
which is why I referred to the library implementation for a better
answer.  This wastes a bunch of zips and does a lot of unnecessary
iteration, which are easily removed from the algorithm, but lead to
difficult to read code; see the library implementation (available at
http://scutil.com/ ).

However, to make the strategy clear:


-module(list_rotate).
-export([rotate/1]).

rotate(Input) ->
   [HeadRow,_] = Input,
   rotate(lists:reverse(Input), lists:duplicate(length(HeadRow),[])).

rotate([], OutRows) -> lists:reverse(OutRows);
rotate([ThisRow|RemInput], OutRows) ->
   rotate(RemInput, [ [NewPrefix]++EachRow || {NewPrefix, EachRow} <-
lists:zip(ThisRow, OutRows) ]).


3284> list_rotate:rotate([[0, 1, 0, 0],
3284>  [0, 1, 1, 0],
3284>  [0, 0, 1, 0],
3284>  [0, 0, 0, 0]]).
[[0,0,0,0],[0,1,1,0],[1,1,0,0],[0,0,0,0]]


Doing something like this is both easier and much faster on tuples, at
which point Mr. Billquist's strategy of construction through item
lookup becomes the preferred method (in lists, the cost of iterating
each list for each item is prohibitive.)


More information about the erlang-questions mailing list