Find index span of a sub list from a list

Question

Given a list of string L, and a sublist M from L. I want to find an efficient way to find the index span (index_a, index_b) from L where L[index_a: index_b] = M.

For example,

L = ['Clement', 'Joseph', 'Man', '##ey', 'was', 'an', 'American', 'businessman', 'from', 'Boston', 'who', 'was', 'president', 'of', 'a', 'contracting', 'company', 'and', 'a', 'minority', 'owner', 'and', 'treasurer', 'of', 'the', 'Boston', 'Braves', 'baseball', 'team', '.']
M = ['Clement', 'Joseph', 'Man', '##ey']

Expected_result = (0,4) # since L[0:4] = M

L = ['Clement', 'Joseph', 'Man', '##ey', 'was', 'an', 'American', 'businessman', 'from', 'Boston', 'who', 'was', 'president', 'of', 'a', 'contracting', 'company', 'and', 'a', 'minority', 'owner', 'and', 'treasurer', 'of', 'the', 'Boston', 'Braves', 'baseball', 'team', '.']
M = ['Boston']

Expected_result = (9,9) # both (9,9) and (25,25) are correct since L[9]=L[25]=M

jizhihaoSAMA · Accepted Answer · 2020-12-08T09:36:54.773

Use a comprehension,and check the length when return the value:

def getIndex(lst1, lst2):
    index1 = next((i for i in range(len(lst1) - len(lst2)) if lst1[i:i + len(lst2)] == lst2), None)
    if index1 is not None: # when sub list doesn't exist in another list
        return (index1, index1) if len(lst2) == 1 else (index1, index1+len(lst2))
    else:
        return None

L1 = ['Clement', 'Joseph', 'Man', '##ey', 'was', 'an', 'American', 'businessman', 'from', 'Boston', 'who', 'was',
     'president', 'of', 'a', 'contracting', 'company', 'and', 'a', 'minority', 'owner', 'and', 'treasurer', 'of', 'the',
     'Boston', 'Braves', 'baseball', 'team', '.']
M1 = ['Clement', 'Joseph', 'Man', '##ey']

L2 = ['Clement', 'Joseph', 'Man', '##ey', 'was', 'an', 'American', 'businessman', 'from', 'Boston', 'who', 'was', 'president', 'of', 'a', 'contracting', 'company', 'and', 'a', 'minority', 'owner', 'and', 'treasurer', 'of', 'the', 'Boston', 'Braves', 'baseball', 'team', '.']
M2 = ['Boston']

print(getIndex(L1, M1))
print(getIndex(L2, M2))

Result:

(0, 4)
(9, 9)

Or one line:

def getIndex(lst1, lst2):
    return next(((i, i + (len(lst2) if len(lst2) > 1 else 0)) for i in range(len(lst1) - len(lst2)) if lst1[i:i + len(lst2)] == lst2), None)

Thanks for the solution. I am not very familiar with the `next` function and I wonder whether using it would be more efficient than using a simple loop over the list? — Garvey, Dec 08 '20 at 09:41
@Garvey Check this:https://stackoverflow.com/questions/30245397/why-is-a-list-comprehension-so-much-faster-than-appending-to-a-list. — jizhihaoSAMA, Dec 08 '20 at 09:45

score 1 · Answer 2 · answered Dec 08 '20 at 09:26

1

def getIndices(L,M):
    results = []
    for i in range(len(L) - len(M)):
        if L[i:i+len(M)] == M:
            results.append((i, i+len(M)))
    return results

Traversing the list L in blocks of len(M)and checking if it's equal to the list M

answered Dec 08 '20 at 09:26

Suraj

2,253
3
17
48

Find index span of a sub list from a list

2 Answers2