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

Question

这是我的示例数据结构：

r代表行。

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

我将如何找到路径不能相同的所有路径，路径只能从水平开始遍历（并且仅从第 0 行开始），然后是垂直遍历，然后是水平遍历，等等，在路径中不能选择相同的值。如果在当前 row/column.

中检测到有效值，则路径可以“跳跃”值

行和列从索引0开始。

未来算法输出的预期路径示例：

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

// Trying to replicate output 00(E9), 10(1C), 11(E9), 01(55), 02(1C), 12(E9), 22(55), 21(1C), 20(BD)

const algo = (values) => {
  // Find the number of keys of the values/data object
  const totalKeys = Object.keys(values).length

  // Cycle through the keys with an assumption that the first key is always 'r0'
  for (let row = 0; row < totalKeys; row++) {
    // construct a key name
    const keyName = "r" + row

    // get the array associated with this key
    const arr = values[keyName]

    // loop through the array
    for (let column = 0; column < arr.length; column++) {
      // get the current value
      const value = arr[column]

      // do whatever you want to do with values, I am just printing them here
      console.log("" + row + column + "(" + value + ")")
    }
  }
}

const data = { // usage of var is discouraged, use let or const instead
  r0: ["E9", "55", "1C"],
  r1: ["1C", "E9", "E9"],
  r2: ["BD", "1C", "55"]
}

algo(data);

Answer 2

此答案中使用的规则

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

从0_0开始
从横向开始
每一步交替horizontal/vertical
永远不要访问同一个单元格两次
我们可以跳过已经访问过的单元格
路径不必覆盖整个网格

算法

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

在下面的例子中，它需要2个参数：

路径: 已访问单元格数组
horizontal: 一个布尔值，描述我们是否应该水平移动

我们第一次调用它时，我们给它一个包含第一个单元格 (['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(' '))
);

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

How do I find all permutations from a series of arrays that act as rows and columns in javascript?

javascript

arrays

path

permutation

此答案中使用的规则

算法

代码