CODEWITHSUNDEEP
python-3.xlistintersection
Peter.k
Peter.k

Reputation: 1548

How to find indices of two lists intersection using Python?

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.

Upvotes: 1

Views: 199

Answers (2)

blhsing
blhsing

Reputation: 107134

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]

Upvotes: 1

Thierry Lathuille
Thierry Lathuille

Reputation: 24291

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.

Upvotes: 1

Related Questions