python - Find overlap of two lists, preserving sequence order -

python - Find overlap of two lists, preserving sequence order -

i've found many methods of finding list intersections here, i'm having problem finding efficient way find intersection when order taken account.

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

the function should homecoming [3, 4, 5]

i know there 1 overlapping sequence, , know minimum length, not exact length.

you looking longest mutual subsequence algorithm; next uses dynamic programming find elements in o(nm) time (for sequences of length n , m):

def lcs(a, b): tbl = [[0 _ in range(len(b) + 1)] _ in range(len(a) + 1)] i, x in enumerate(a): 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 , j: if tbl[i][j] == tbl[i - 1][j]: -= 1 elif tbl[i][j] == tbl[i][j - 1]: j -= 1 else: res.append(a[i - 1]) -= 1 j -= 1 homecoming res[::-1]

demo:

>>> def lcs(a, b): ... tbl = [[0 _ in range(len(b) + 1)] _ in range(len(a) + 1)] ... i, x in enumerate(a): ... 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 , j: ... if tbl[i][j] == tbl[i - 1][j]: ... -= 1 ... elif tbl[i][j] == tbl[i][j - 1]: ... j -= 1 ... else: ... res.append(a[i - 1]) ... -= 1 ... j -= 1 ... homecoming res[::-1] ... >>> list1 = [1, 2, 3, 4, 5, 6, 7] >>> list2 = [7, 6, 3, 4, 5, 8] >>> lcs(list1, list2) [3, 4, 5]

this find subsequence regardless of location , if other elements mixed in between:

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

python list