How to find indices of two lists intersection using Python?

Question

I have 2 lists:

l1 = ['oak', 'tree', ',', 'tree', 'preservation', 'order', 'to',
 'be', 'crowned', 'and', 'cleared', 'of', 'deadwood']
l2 =  ['tree', 'preservation', 'order']

I need to find indices of intersection of these. Result should be just a list of[3,4,5].

The problem is algorithms I found returns wrong values. For example:

def find_matching_indices(a, b):
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            if x == y:
                yield i, j

returns [(1, 0), (3, 0), (4, 1), (5, 2)] so it consideres all matches not the whole list within list.

Wouldn't you expect [1, 3, 4, 5]? [i for i, val in enumerate(l1) if val in l2] — solbs, Apr 04 '19 at 21:31
Possible duplicate of [elegant find sub-list in list](https://stackoverflow.com/questions/10106901/elegant-find-sub-list-in-list) — joel, Apr 04 '19 at 21:32
@lil_solbs I think they're looking for `l2` to be present in its entirety as a sublist of `l1`. — mypetlion, Apr 04 '19 at 21:41
this should help https://stackoverflow.com/a/3697438/9754169 — Yuca, Apr 04 '19 at 21:44

score 1 · Answer 1 · answered Apr 04 '19 at 21:34

This is not the most efficient algorithm, but you can do:

l1 = ['oak', 'tree', ',', 'tree', 'preservation', 'order', 'to',
 'be', 'crowned', 'and', 'cleared', 'of', 'deadwood']
l2 =  ['tree', 'preservation', 'order']

def intersection(l1, l2):            
    for i in range(len(l1)-len(l2)+1):
        if l1[i:i+len(l2)] == l2:
            return [j for j in range(i, i+len(l2))]

print(intersection(l1, l2))
# [3, 4, 5]

It just compares the short l2 list with successive slices of l1. When they match, it creates the list of matching indices.

score 1 · Accepted Answer · answered Apr 04 '19 at 21:48

1

You can use collections.deque with a maximum length of the size of l2 and enqueue items of l1 into it to act as a rolling window. Output the current index plus the ones before it up to the length of l2 if the content of the queue matches that of l2:

from collections import deque
q = deque(maxlen=len(l2))
for i, s in enumerate(l1):
    q.append(s)
    if list(q) == l2:
        print(list(range(i - len(l2) + 1, i + 1)))

This outputs:

[3, 4, 5]

answered Apr 04 '19 at 21:48

blhsing

91,368
6
71
106

1

Thanks. Tested many solutions and I think it's optimal way to do it. – Peter.k Apr 05 '19 at 10:08

How to find indices of two lists intersection using Python?

2 Answers2