在兩個不同長度的不相同的未排序python列表中匹配/連接元素的最佳方法是什麼？

Question

我具有例如以下Python列表：

a = [1,2,1,3,2,1,1,1,2,1,1,1,1,1,3,1,2] 
b = [1,1,2,1,3,1,1,1,1,2,2,1,1,1,1,3,1,2] 

和我想獲得可以自信地匹配元素的指數，如的元組：

[(0,0), (1,2), (2,3), (3,4), (8,9), (14,15), (15,16), (16,17)] 

數據表示記錄到達和離開隊列的人數的大小，但數據也不完美，因此a和b的總和不匹配，人們並不總是需要按照他們的順序離開到達。

我意識到它取決於幾個變量（或閾值參數），但我只是尋求有關如何最好地解決問題的建議。我很樂意使用Pandas/Numpy/Scipy來完成這項工作。

我意識到這很難解釋。通過眼睛，我很容易匹配部分序列，例如1,2,1,3。儘管如此，沒有發現它很容易找出一個好的算法。

Answer 1

我終於實現的Python有difflib圖書館只是這種事情！

a = [1, 2, 1, 3, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2] 
b = [1, 1, 2, 1, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 2] 

from difflib import SequenceMatcher 

s = SequenceMatcher(None, a, b, autojunk=False) 

matched_element_indices = [] 
for m in s.get_matching_blocks(): 
    matched_element_indices += [(m.a+i,m.b+i) for i in range(m.size)] 

它產生這樣的：

In : matched_element_indices 
Out: [(0, 1), (1, 2), (2, 3), (3, 4), (5, 6), (6, 7), (7, 8), (8, 9), 
      (10, 11), (11, 12), (12, 13), (13, 14), (14, 15), (15, 16), (16, 17)] 

Answer 2

我不完全理解你的輸出，但得到的匹配元素指標依次是：

a = [1, 2, 1, 3, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2] 
b = [1, 1, 2, 1, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 2] 
from collections import defaultdict, deque 

d = defaultdict(deque) 
for i, j in enumerate(b): 
    d[j].append(i) 

print([(i, d[j].popleft()) for i, j in enumerate(a)]) 

我可以匹配你的輸出的唯一方法是，如果我們考慮不序列元素：

from itertools import groupby 
from operator import itemgetter 

def pairs(a, b): 
    for (k, v) in (groupby(enumerate(a), key=itemgetter(1))): 
     data = next(v) 
     if not next(v, None): 
      ind, val = data 
      if b[ind] == val: 
       yield (ind, ind) 
      elif val == b[ind + 1]: 
       yield (ind, ind + 1) 

print(list(pairs(a, b))) 

這將使你：

[(0, 0), (1, 2), (2, 3), (3, 4), (8, 9), (14, 15), (15, 16), (16, 17)]