在给定的n*m矩阵中匹配一个序列的算法

Question

我有一个n*m维的矩阵，并且我想要匹配一组数字与给定的矩阵。如果样式在矩阵的垂直或水平列中，这是相当简单的，但如果样式呈对角线形式，则无法检测到它。例如，如果我必须在以下矩阵中匹配给定模式[-1，-1，-1]，则应该能够检测到对角线方式中的-1组，以及最后一行中的-1组。

0 0 0 -1 0 0 0 -1 0 0 0 -1 0 0 0 1 0 -1 -1 -1

在上述情况下，我应该能够检测到右至左的对角线和最后一行序列。基本上，在给定的序列中，我必须能够检测到它的存在，它可以以垂直方式、水平方式或对角线方式出现。我的问题是：算法必须检测“所有”序列，不管它们是水平、垂直还是对角线出现。另外，请注意矩阵的维度是N*M，因此它可以是任何大小。

- Rahul

---

你的问题是什么？ - Tom Zych

你的算法需要找到全部吗？还是只需要找到一个？例如：在你最后一个矩阵中，它应该找到所有的3吗？ - corsiKa

每个位置上的数字总是相同的吗 -- 你从不需要匹配，例如 [1 2 3]？ - Hot Licks

glowcoder：在我的最后一个矩阵中，只有两个相似的模式——从左上角开始的-1和最后一行的-1序列。 - Rahul

Answer 1

我注意到您可以（比较详尽地）迭代n行m列矩阵（视为单个向量），并使用不同的步幅——1、m-1、m、m+1。在每个步幅开始时，从每个位置开始（直到此步幅超出向量的末尾为止），看看是否有匹配项。

这至少消除了水平、垂直和两个对角线的四种不同算法。

然而，从算法顺序上来看，非常丑陋--几乎是N平方的。

（嗯，也许不是。您可以使用单个循环限定起始单元格，适用于所有四种可能性。因此，一旦找到起点，请检查四个步幅。所以，您应该能够通过矩阵进行一次基本遍历来检查所有内容。）

- Hot Licks

---

Daniel，你能举个例子详细说明一下你的解决方案吗？我不明白不同步长如何避免使用4种不同的算法。 - Rahul

一个算法，4个步骤。将您上面的4 x 5示例“向量化”，从开头开始扫描第一个匹配数字，然后依次使用1、3、4和5的步幅来检查剩余的数字。 - Hot Licks

Answer 2

虽然这是一个老问题，但我希望我的答案能对某些人有所帮助。

在开发井字棋项目时，我尝试推广一种解决方案，我认为它也适用于你的问题。此实现将寻找“线条模式”（这意味着它仅适用于水平/垂直/对角线上的元素序列）。

function lookForCombinationsOnGrid(grid, ...args) {
/* This function looks for a linear sequence of elements (x, o, undefined) 
on the grid. 
It returns an array of all beginning and ending coordinates (x, y) for 
the corresponding pattern. 
Inputs:
- grid, a system of coordinates with an x-axis and an inverted y-axis.   
- elements can be any sort of built-in objects. 
*/

let sequence = [];
sequence.push(args[0]);
args.reduce(function (accumulator, currentValue, currentIndex, args) {
    return sequence.push(currentValue);
});
console.log("sequence =", sequence);

let testedArr;
// Look for this combination horizontally. 
let result1 = [];
for (i = 0; i < grid.length; i++) {
    for (j = 0; j <= grid[i].length - sequence.length; j++) {
        testedArr = [];
        for (k = 0; k < sequence.length; k++) {
            testedArr.push(grid[i][j + k]);
        }
        if (testedArr.join() === sequence.join()) {
            let start = [j, i];
            let end = [j + sequence.length - 1, i];
            result1.push([start, end]);
        }
    }
}
console.log("Found", result1.length, "results horizontally. ");

// Look for this combination vertically. 
let result2 = [];
for (i = 0; i < grid[0].length; i++) {
    for (j = 0; j <= grid.length - sequence.length; j++) {
        testedArr = [];
        for (k = 0; k < sequence.length; k++) {
            testedArr.push(grid[j + k][i]);
        }
        if (testedArr.join() === sequence.join()) {
            let start = [i, j];
            let end = [i, j + sequence.length - 1];
            result2.push([start, end]);
        }
    }
}
console.log("Found", result2.length, "results vertically. ");

// Look for this combination diagonally. 
let result3 = [];
for (i = 0; i <= grid.length - sequence.length; i++) {
    for (j = 0; j <= grid[i].length - sequence.length; j++) {
        testedArr = [];
        for (k = 0; k < sequence.length; k++) {
            testedArr.push(grid[i + k][j + k]);
        }
        if (testedArr.join() === sequence.join()) {
            let start = [j, i];
            let end = [j + sequence.length - 1, i + sequence.length - 1];
            result3.push([start, end]);
        }
    }
}
console.log("Found", result3.length, "results diagonally (left to right). ");

// and diagonally the other way... 
let result4 = [];
for (i = 0; i <= grid.length - sequence.length; i++) { // line i = 0
    for (j = grid[i].length-1 ; j >= 0 + sequence.length-1; j--) { // column j = 1
        testedArr = [];
        for (k = 0; k < sequence.length; k++) {
            testedArr.push(grid[i + k][j - k]); // + 1 line to i, -1 col to j
        }
        if (testedArr.join() === sequence.join()) {
            let start = [j, i];
            let end = [j - sequence.length + 1, i + sequence.length - 1];
            result4.push([start, end]);
        }
    }
}
console.log("Found", result4.length, "results diagonally (right to left). ");

let result = result1.concat(result2);
result = result.concat(result3);
result = result.concat(result4);

return result;
}
grid = [[1, 1, 3],
        [1, 1, 1],
        [1, 1, 1],
        [0, 1, 1]];
console.log(lookForCombinationsOnGrid(grid, 1, 1, 1, 0 ));

我希望这能帮助到某个人。

- edmond

Answer 3

无论优化技术如何，这个问题的更通用版本如下：

您有一个元素数组，其中每个元素都是一个数字，并且相对于彼此的位置。

例如，从左到右的数字列表60、50、40、30看起来像(60,0,0) (50,1,0) (40,2,0) (30,3,0)。如果这是一个从上到下的列表，它将是(60,0,0) (50,0,1) (40,0,2) (30,0,3)。如果它是从左上到右下的对角线，则为(60,0,0) (50,1,1) (40,2,2) (30,3,3)。

因此，以这种方式，问题已经变得更加通用：您想在矩阵中找到一组可以指定坐标方向的数字列表。

然后，通用算法看起来像这样：

For each configuration
    For each coordinate of the matrix
        For each element in the list and corresponding local coordinate
            Add the local coordinate to the coordinate within the matrix
            If the value at that coordinate in the matrix does not match go to next configuration
    We found a match! Prosperity and happiness!

通常，魔鬼就在细节中。具体而言，在这种情况下，您实际上不想遍历矩阵的所有坐标。您真正想要的是遍历所有坐标，当它们与模式相加时，会产生匹配的可能性，同时不会超出矩阵范围。（这样就可以减少很多错误检查。）

这是一个简单的二维剪切问题。在配置的相对定位值中找到最低的X和Y以及最高的X和Y。如果您正在使用基于零索引的矩阵，则希望您的起始坐标为-lowX，-lowY，并且您的最大坐标为matrixMaxX - 1 - highX，matrixMaxY - 1 - highY。

另一个好处是，您可以添加任何形状，而不仅仅是上/下/左/右/四个对角线。但这取决于您。

- Kaganar