Python: Finds a public sublist of a given length that exists in two lists

Python: Finds a public sublist of a given length that exists in two lists … here is a solution to the problem.

Python: Finds a public sublist of a given length that exists in two lists

I had to find an efficient python code to do the following:

Find at least one n consecutive sequence of elements contained in two given lists, if one exists.

For example, n=3, the result of these two lists will be [‘Tom’, ‘Sam', 'Jill']:

lst1 = ['John', 'Jim', 'Tom', 'Sam', 'Jill', 'Chris']
lst2 = ['Chris', 'John', 'Tom', 'Sam', 'Jill', 'Jim']

The following sample code does the trick, but if I have to compare hundreds of thousands of rows/lists, I need to do the same thing forever. Any suggestions on how to optimize the performance of this code for handling large amounts of data would be appreciated!

lst1 = ['John', 'Jim', 'Tom', 'Sam', 'Jill', 'Chris']
lst2 = ['Chris', 'John', 'Tom', 'Sam', 'Jill', 'Jim']
strNum = 3 #represents number of consecutive strings to search for
common_element_found = 'False'
common_elements = []

lst1length = len(lst1) - (strNum - 1)
lst2length = len(lst2) - (strNum - 1)
for x in range(lst1length):
    ConsecutiveStringX = lst1[x] + ' ' + lst1[x + 1] + ' ' + lst1[x + 2]
    for y in range(lst2length):
        ConsecutiveStringY = lst2[y] + ' ' + lst2[y + 1] + ' ' + lst2[y + 2]
        if ConsecutiveStringY == ConsecutiveStringX:
            common_element_found = 'True'
            common_elements.append(ConsecutiveStringY)
            print('Match found: ' + str(common_elements)) 
            break
    if common_element_found == 'True':
        common_element_found = 'False'
        break

Solution

International Confederation of Industry,

consecs1 = [ tuple(lst1[i:i+3]) for i in range(0, len(lst1)-2)]
consecs2 = { tuple(lst2[i:i+3]) for i in range(0, len(lst2)-2)}

for c in consecs1: 
    if c in consecs2:
         print(c)

Output

('Tom', 'Sam', 'Jill')

Description: You can make a list of tuples for lst1, which are hashable objects, and check if they are in the collection of >tuples built from lst2 (it provides O(1) speed).

PS: Although the set is unordered, the order is guaranteed because the loop follows lst1 instead of lst2 order.

Related Problems and Solutions