查找兩個列表的重疊，保留序列的順序

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]