如何在二维列表中查找与特定模式匹配的元素

Question

我想找到一种有效的方法来检索数组中与特定模式匹配的所有元素。

例如，考虑到我有：

一个数组M由不同大小的子数组组成：

  M = [[0, 1],
       [3, 2, 4],
       [3, 8],
       [9],
       [0, 2],
       [3, 1],
       [0, 3],
       [2, 4],
       [3, 7]]

子数组的模式。例如，[[a, b], [a, c], [a, d]] 匹配 [[0, 1], [0, 2], [0, 3]].

如何 return M 的所有元素对应于模式？

到目前为止，我一直在使用 for 循环来查找匹配元素，但是当模式具有 2 个以上的子数组时，这种幼稚的方法被证明是非常昂贵的。

示例：

M = [[0, 1], [3, 2, 4], [3, 8], [9], [0, 2], [3, 1], [0, 3], [2, 4], [3, 7]]

# pattern with 3 sub-arrays -> [[a, b], [a, c], [a, d]]

for i, arr1 in enumerate(M):
    for j, arr2 in enumerate(M):
        for k, arr3 in enumerate(M):
            if i != j != k:
                if len(arr1) == len(arr2) == len(arr3) == 2:
                    a1, a2, a3 = arr1[0], arr2[0], arr3[0]
                    b, c, d = arr1[1], arr2[1], arr3[1]
                    if a1 == a2 == a3 and b < c < d:
                        print arr1, arr2, arr3

输出：

[0,1], [0,2], [0,3]
[3,1], [3,7], [3,8]

由于每个子数组占一个额外的嵌套循环，这种方法的时间复杂度（O(n^k) 其中 k 是子数组的数量）成为一个问题。

是否可以加快这个过程？如果可以，怎么做？

Answer 1

首先，在进入 numpy 之前，让我们先看看您的情况。您要求 sub-arrays 只有两个元素。所以让我们pre-filter你的数组：

M = [m for m in M if len(m) == 2]

现在您正在检查 a1 == a2 == a3 and b < c < d，但是 b、c、d 的每个可能排列都显示在序列中。所以真的，如果你找到 any b != c != d 对于给定的 a，你可以将它重新排列到正确的顺序，知道那个顺序最终会出现。

因此，处理此问题的一个非常简单的方法是构造一个字典映射 a 到 b、c、d 的所有可能选项，然后过滤它们您想要的“子数组”的最小数量，对它们进行排序，并计算所有可能的组合：

# set removed duplicates automatically
options = collections.defaultdict(set)

for a, b in (m for m in M if len(m) == 2):  # Use a generator to filter on-the-fly
    options[a].add(b)

for a, bcd in options.items():
    # sort (combinations automatically filters too-short bins)
    for b, c, d in itertools.combinations(sorted(bcd), 3):
        print(f'[{a}, {b}], [{a}, {c}], [{a}, {d}]')

这个解决方案在算法上可能是最优的。它对初始列表进行单次传递以识别潜在模式，然后对每个模式执行一次迭代。这里唯一可能缺少的是完全消除了重复项。您可以使用 collections.Counter 而不是 set.

来处理重复项

如何在二维列表中查找与特定模式匹配的元素

How to find elements that match a specific pattern in a 2d list

python

optimization

pattern-matching