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

Question

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

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

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

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

Answer 1

您正在寻找Longest Common Subsequence算法;下面使用动态规划在 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]