I'm trying to transpose a matrix using recursion. Now, I know that under normal circumstances this isn't a good idea and a nested loop/nested map, or a similar approach is superior, but I need to learn this for educational purposes.

To show that I did my homework, here is the nested loop approach:

const arrMatrix = [
  [3, 6, 7, 34],
  [6, 3, 5, 2],
  [2, 6, 8, 3]
];

const transposedMatrix = []

for (let i = 0; i < arrMatrix[0].length; i++) {
  const tempCol = [];
  for (let j = 0; j < arrMatrix.length; j++) {
    tempCol.push(arrMatrix[j][i]);
  }
  transposedMatrix.push(tempCol);
}

console.log(transposedMatrix);

I'm trying to transpose a matrix using recursion. Now, I know that under normal circumstances this isn't a good idea and a nested loop/nested map, or a similar approach is superior, but I need to learn this for educational purposes.

To show that I did my homework, here is the nested loop approach:

const arrMatrix = [
  [3, 6, 7, 34],
  [6, 3, 5, 2],
  [2, 6, 8, 3]
];

const transposedMatrix = []

for (let i = 0; i < arrMatrix[0].length; i++) {
  const tempCol = [];
  for (let j = 0; j < arrMatrix.length; j++) {
    tempCol.push(arrMatrix[j][i]);
  }
  transposedMatrix.push(tempCol);
}

console.log(transposedMatrix);

Here's another approach using nested maps:

    const arrMatrix = [
      [3, 6, 7, 34],
      [6, 3, 5, 2],
      [2, 6, 8, 3]
    ];

    const transposedMatrix = arrMatrix[0].map((_, i) =>
      arrMatrix.map((_, j) => arrMatrix[j][i])
    );

    console.log(transposedMatrix);

Here are some resources that I went through but didn't manage to e up with a solution using them.

If possible, in addition to the algorithm/code, please give me some explanation and resources to learn more about it.

• javascript
• algorithm
• recursion
• functional-programming

5 Answers 5

  const map = ([head, ...tail], mapper) => tail.length ? [mapper(head), ...map(tail, mapper)] : [mapper(head)];

  const transpose = matrix =>
    matrix[0].length 
      ? [map(matrix, row => row.shift()), ...transpose(matrix)]
      :  [];

How it works:

From a given matrix, we always take out the first column (matrix.map(row => row.shift()), then we continue recursively:

 [[1, 1, 1],    ->   [[1, 1],    ->  [[1],   ->   [[],
  [2, 2, 2],          [2, 2],         [2],         [],
  [3, 3, 3]]          [3, 3]]         [3]]         []]

Then the base case gets reached, the matrix is empty (matrix[0].length is 0 = falsy) and an empty array gets returned. Now at every step, the column taken out gets added to that array, and thus it's a row now:

   [[1, 2, 3],    <-    [[1, 2, 3],    <-  [[1, 2, 3]]   <-  []
    [1, 2, 3],            [1, 2, 3]]    
    [1, 2, 3]]

Note: This destroys the original array.

const transpose = matrix => {
  const row = (x) => x >= matrix[0].length ? [] : [col(x, 0), ...row(x + 1)];
  const col = (x, y) => y >= matrix.length ? [] : [matrix[y][x], ...col(x, y + 1)];
  return row(0);
};

That version does not mutate the original array. You can take that even a step further, than it is purely functional, but thats a bit overkill:

 const transpose = matrix => (
   (row, col) => row(row)(col)(0)
 )(
    row => col => (x) => x >= matrix[0].length ? [] : [col(col)(x, 0), ...row(row)(col)(x + 1)],
    col => (x, y) => y >= matrix.length ? [] : [matrix[y][x], ...col(col)(x, y + 1)]
 );

This is very similar to hitmands' solution, and would likely be less performant, but I think it's slightly cleaner to avoid working with column indices:

const head = xs => xs[0]
const tail = xs => xs.slice(1)

const transpose = (m) => head(m).length
  ? [m.map(head), ...transpose(m.map(tail))]
  : []

const matrix = [
  [3, 6, 7, 34],
  [6, 3, 5, 2],
  [2, 6, 8, 3]
]

console .log (
  transpose (matrix)
)

This version transposes the first column into a row (via .map(head)) and then recurs on the remaining matrix (via .map(tail)), bottoming out when the first row is empty. You can inline those helper functions if you choose, so that it looks like this:

const transpose = (m) => m[0].length
  ? [m.map(xs => xs[0]), ...transpose(m.map(xs => xs.slice(1)))]
  : []

..but I wouldn't remend it. The first version seems more readable, and head and tail are easily reusable.

Update

user633183 suggests an alternative escape condition. It's a good question whether or not it's a better result for ill-formed data, but it's certainly a useful possible variant:

const head = xs => xs[0]
const tail = xs => xs.slice(1)
const empty = xs => xs.length == 0

const transpose = (m) => m.some(empty)
  ? []
  : [m.map(head), ...transpose(m.map(tail))]

(This could also be done with m.every(nonempty) by reversing the consequent and alternative in the conditional expression, but I think it would be slightly harder to read.)

I would write it like this, assuming that all the rows inside the matrix have the same length:

1. check if there still are rows to process
2. create a row from each colum at the given index
3. increment column index by 1
4. call transpose with the new index

const transpose = (m, ci = 0) => ci >= m[0].length 
  ? [] 
  : [m.map(r => r[ci]), ...transpose(m, ci + 1)]
;


const matrix = [
  [3, 6, 7, 34],
  [6, 3, 5, 2],
  [2, 6, 8, 3]
];

console.log(
  transpose(matrix),
);

I had an idea to write transpose using the Maybe monad. I'll start using functional operations and then refactor to clean up the code -

Dependencies -

const { Just, Nothing } =
  require("data.maybe")

const safeHead = (a = []) =>
  a.length
    ? Just(a[0])
    : Nothing()

const tail = (a = []) =>
  a.slice(1)

Without refactors -

const column = (matrix = []) =>
  matrix.reduce
    ( (r, x) =>
        r.chain(a => safeHead(x).map(x => [ ...a, x ]))
    , Just([]) 
    )

const transpose = (matrix = []) =>
  column(matrix)
    .map(col =>
      [ col, ...transpose(matrix.map(tail)) ]
    )
    .getOrElse([])

Refactor column using generic append and lift2 -

const append = (a = [], x) =>
  [ ...a, x ]

const lift2 = f =>
  (mx, my) =>
    mx.chain(x => my.map(y => f(x, y)))

const column = (matrix = []) =>
  matrix.reduce
    ( (r, x) =>
        lift2(append)(r, safeHead(x))
    , Just([])
    )

const transpose = (matrix = []) =>
  column(matrix)
    .map(col =>
      [ col, ...transpose(matrix.map(tail)) ]
    )
    .getOrElse([])

Refactor column again using generic transducer mapReduce -

const mapReduce = (map, reduce) =>
  (r, x) => reduce(r, map(x))

const column = (matrix = []) =>
  matrix.reduce
    ( mapReduce(safeHead, lift2(append))
    , Just([]) 
    )

const transpose = (matrix = []) =>
  column(matrix)
    .map(col =>
      [ col, ...transpose(matrix.map(tail)) ]
    )
    .getOrElse([])

transpose stays the same in each refactoring step. It produces the following outputs -

transpose
  ( [ [ 1, 2, 3, 4 ]
    , [ 5, 6, 7, 8 ]
    , [ 9, 10, 11, 12 ]
    ]
  )
  // [ [ 1, 5, 9 ]
  // , [ 2, 6, 10 ]
  // , [ 3, 7, 11 ]
  // , [ 4, 8, 12 ]
  // ]

transpose
  ( [ [ 1, 2, 3, 4 ]
    , [ 5 ]
    , [ 9, 10, 11, 12 ]
    ]
  )
  // [ [ 1, 5, 9 ] ]