查找两个列表的重叠，保留序列顺序

Question

我在这里找到了许多查找列表交集的方法，但在考虑顺序时，我很难找到一种有效的方法来查找交集。

list1 = [1, 2, 3, 4, 5, 6, 7]
list2 = [7, 6, 3, 4, 5, 8]

函数应返回[3, 4, 5]

我已经知道只有一个重叠序列，我知道它的最小长度，但不知道它的确切长度。

Answer 1

您正在寻找最长公共子序列算法；以下使用动态编程来查找O（NM）时间中的元素（对于长度为N和M的序列）：

def lcs(a, b):
    tbl = [[0 for _ in range(len(b) + 1)] for _ in range(len(a) + 1)]
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            tbl[i + 1][j + 1] = tbl[i][j] + 1 if x == y else max(
                tbl[i + 1][j], tbl[i][j + 1])
    res = []
    i, j = len(a), len(b)
    while i and j:
        if tbl[i][j] == tbl[i - 1][j]:
            i -= 1
        elif tbl[i][j] == tbl[i][j - 1]:
            j -= 1
        else:
            res.append(a[i - 1])
            i -= 1
            j -= 1
    return res[::-1]

演示：

>>> def lcs(a, b):
...     tbl = [[0 for _ in range(len(b) + 1)] for _ in range(len(a) + 1)]
...     for i, x in enumerate(a):
...         for j, y in enumerate(b):
...             tbl[i + 1][j + 1] = tbl[i][j] + 1 if x == y else max(
...                 tbl[i + 1][j], tbl[i][j + 1])
...     res = []
...     i, j = len(a), len(b)
...     while i and j:
...         if tbl[i][j] == tbl[i - 1][j]:
...             i -= 1
...         elif tbl[i][j] == tbl[i][j - 1]:
...             j -= 1
...         else:
...             res.append(a[i - 1])
...             i -= 1
...             j -= 1
...     return res[::-1]
... 
>>> list1 = [1, 2, 3, 4, 5, 6, 7]
>>> list2 = [7, 6, 3, 4, 5, 8]
>>> lcs(list1, list2)
[3, 4, 5]

这将找到子序列，无论位置如何，如果其他元素混合在两者之间：

>>> lcs([1, 2, 3, 4, 5, 6, 7], [7, 3, 6, 4, 8, 5])
[3, 4, 5]