javascript - 如何使用递归转置 m*n 矩阵？

Question

我正在尝试使用递归转置矩阵。现在，我知道在正常情况下这不是一个好主意，嵌套循环/嵌套映射或类似的方法更好，但出于教育目的我需要了解这一点。

为了证明我做了功课，这里是嵌套循环方法:

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

这是使用嵌套 map 的另一种方法:

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

这是 some resources我经历过但没能想出使用它们的解决方案。

如果可能，除了算法/代码，请给我一些解释和资源以了解更多信息。

Answer 1

  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)]
      :  [];

工作原理:

我们总是从给定的矩阵中取出第一列 (matrix.map(row => row.shift())，然后我们继续递归:

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

然后达到基本情况，矩阵为空(matrix[0].length 为 0 = falsy)并返回一个空数组。现在在每一步中，取出的列都会添加到该数组中，因此它现在是一行:

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

---

注意:这会破坏原始数组。