如何从第一个到最后一个二维数组中找到所有可能的路径，其中每个步骤的值都大于上一步？

Question

到目前为止，我得到的代码只找到了 2 条可能的路径。我怎样才能重新处理它以找到所有这些？

有效路径的一个例子是，从第一个数组 [1, 32] 开始。选择一个数字作为步进的起点，例如 32.

查看下面的下一个数组：[11, 21, 24, 27, 35, 37, 65]。一个有效的步骤是这些数字中的任何一个大于您当前的步骤。所以 35、37 和 65 都是有效的步骤。

并继续构建路径，按顺序（从上到下）进入其他阵列，直到到达最后一个。

'use strict';

const matrix = [
  [1, 32],
  [11, 21, 24, 27, 35, 37, 65],
  [17, 22, 25, 51, 57, 63],
  [18, 56]
];

function findPaths(arrays) {
  const paths = [];
  for (let i = 0; i < arrays[0].length; i++) {
    const path = [arrays[0][i]];
    for (let j = 1; j < arrays.length; j++) {
      for (let y = 0; y < arrays[j].length; y++) {
        if (path[Math.max(0, path.length - 1)] < arrays[j][y]) {
          path.push(arrays[j][y]);
          break;
        }
      }
    }
    paths.push(path);
  }
  return paths;
}

const result = findPaths(matrix);

console.log(result); // [ [ 1, 11, 17, 18 ], [ 32, 35, 51, 56 ] ]

Answer 1

我解决了。这不是最有效的解决方案，但我正在努力。

const data = [
  [1, 32],
  [11, 21, 24, 27, 35, 37, 65],
  [17, 22, 25, 51, 57, 63],
  [18, 56]
];

function findPaths(arrays) {
  const paths = [];
  const maxPaths = arrays.reduce((total, arr) => total *= arr.length || total, 1);
  for (let x = 0; x < maxPaths; x++) {
    for (let i = 0; i < arrays[0].length; i++) {
      const path = [arrays[0][i]];
      for (let j = 1; j < arrays.length; j++) {
        for (let y = 0; y < arrays[j].length; y++) {
          if (path[Math.max(0, path.length - 1)] < arrays[j][y]) {
            if (!paths.some(p => p.toString() == [...path, arrays[j][y]].toString())) {
              path.push(arrays[j][y]);
              break;
            }
          }
        }
      }
      paths.push(path);
    }
  }
  return paths.filter(path => path.length == arrays.length).sort();
}

const result = findPaths(data);

console.log(result);

/*
[
  [ 1, 11, 17, 18 ],  [ 1, 11, 17, 56 ],
  [ 1, 11, 22, 56 ],  [ 1, 11, 25, 56 ],
  [ 1, 11, 51, 56 ],  [ 1, 21, 22, 56 ],
  [ 1, 21, 25, 56 ],  [ 1, 21, 51, 56 ],
  [ 1, 24, 25, 56 ],  [ 1, 24, 51, 56 ],
  [ 1, 27, 51, 56 ],  [ 1, 35, 51, 56 ],
  [ 1, 37, 51, 56 ],  [ 32, 35, 51, 56 ],
  [ 32, 37, 51, 56 ]
]
*/

如何从第一个到最后一个二维数组中找到所有可能的路径，其中每个步骤的值都大于上一步？

How to find all possible paths in 2d array of numbers from the first to the last, where each step's value is greater than the previous step?

javascript

arrays

matrix

multidimensional-array

maze