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

Question

以下是我的示例数据结构：

r代表row。

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

我该如何找到路径不可能相同的所有路径，路径只能从水平方向开始(并且只能从第0行开始(，然后是垂直方向，然后是水平方向，等等，在路径中，它不能选择相同的值。路径可以"；跳跃"；如果在当前行/列中检测到有效值，则返回值。

行和列从索引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

此答案中使用的规则

当我读到你的问题时，我明白规则是：

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

算法

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

在以下示例中，它采用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(' '))
);

Answer 2

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