javascript - 如何从一系列数组中找到所有排列，这些数组在 javascript 中充当行和列？

Question

这是我的示例数据结构:

r 代表行。

var data = {
  r0: ["E9", "55", "1C"],
  r1: ["1C", "E9", "E9"],
  r2: ["BD", "1C", "55"]
}

我将如何找到路径不能相同的所有路径，路径只能从水平开始遍历(并且仅从第 0 行开始)，然后是垂直遍历，然后是水平遍历，等等，在它无法选择的路径中相同的值。但是，如果在当前行/列中检测到有效值，路径可以“跳跃”值。

行和列从索引0开始。

future 算法输出的预期路径示例:

RowColumn(value),....

// these paths stop because there are no more valid vertical or horizontal values to pick.
00(E9), 10(1C), 11(E9), 01(55), 02(1C), 22(55), 12(E9)
02(1C), 22(55), 20(BD), 00(E9), 01(55), 21(1C), 11(E9), 10(1C), 12(E9)

Answer 1

此答案中使用的规则

在阅读您的问题时，我了解到规则是:

• 从0_0开始
• 从横向开始
• 每次移动时水平/垂直交替
• 永远不要访问同一个单元格两次
• 我们可以跳过已经访问过的单元格
• 路径不必覆盖整个网格

算法

要让每条路径都遵循这些规则，您可以使用递归函数(一个调用自身的函数)。

在下面的例子中，它有两个参数:

• 路径:已访问单元格的数组
• horizo​​ntal:一个 bool 值，描述我们是否应该水平移动

我们第一次调用它时，我们给它一个包含第一个单元格的路径 (['0_0'])，并且 true 因为我们必须水平移动。

然后它会:

• 查找与上次访问的单元格在同一行或同一列但尚未添加到路径中的单元格(水平或垂直取决于当前方向)
• 为每个 nextCells 调用自身，将该单元格添加到路径和切换方向

代码

function rowColumn(obj) {
  // Convert the Object to a 2D Array
  const data = Object.values(obj),
        rows = data.length,
        cols = data[0].length,
        res  = [];
  
  function recursive(path, horizontal) {    
    // Get the row or column cells that haven't been visited yet
    const nextCells = getNextCells(path, horizontal);
    
    // If no neighbors were found, push the result and return
    if (!nextCells.length) return res.push(path);
    
    // Apply recursion for all possible neighbors
    nextCells.forEach(cell => recursive(path.concat(cell), !horizontal));
  }
  
  function getNextCells(path, horizontal) {
    const [x, y] = path[path.length - 1].split('_').map(v => +v);
    let cells = [];
    
    if (horizontal) cells = Array.from({length: cols}, (_, i) => `${i}_${y}`);
    else            cells = Array.from({length: rows}, (_, i) => `${x}_${i}`);

    // Remove the cells that have already been visited
    return cells.filter(p => !path.includes(p));
  }
  
  // Start the recursion
  recursive(['0_0'], true);
  // Format the result
  return res.sort((a, b) => a.length - b.length)
            .map(path => path.map(cell => {
              const [x, y] = cell.split('_').map(v => +v);
              return `${x}${y}(${data[y][x]})`;
            }));
}

const data = {
  r0: ["E9", "55", "1C"],
  r1: ["1C", "E9", "E9"],
  r2: ["BD", "1C", "55"],
};

const res = rowColumn(data);
console.log(
  `There are ${res.length} paths possible:`,
  res.map(path => path.join(' '))
);