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

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]