How to compare two lists and decide one matches the other?

Question

For example, I have one list as below:

l1 = [1, 2, 3, 4]

I have another list lx to compare with l1 and need to decide whether lx matches l1. A successful match is defined as below:

For each element e in lx, e must be in l1 too; and for any two sequential elements e1 and e2, if e1 appears before e2, then e1 must also appear before e2 in l1.

Some examples are below and their match status with l1 is provided:

l2 = [2, 1]      # fails
l3 = [1, 2, 4]   # succeeds
l4 = [2, 3]      # succeeds
l5 = [2, 3, 1]   # fails
l6 = [1,2,3,4,5] # fails

UPDATE for more complicated cases:

l1 = [1, 2, 3, 4]
l2 = [{2}, {1}]
l2 = [{2,1}, {1,3}]

l1 doesn't change, but in the other list, it's always a set of lists. For this example:

l2 = [{2,1}, {1,3}]

It can be expanded into:

l2 = [[2,1], [2,3], [1,1], [1,3]] 

which means as long as one of the 4 lists in l2 matches l1, it is a successful match. Since [1,3] matches l1=[1,2,3,4], the whole l2 can match.

So one solution may be first flatten the l2 into the new l2, and then the all(e in i for e in b) can be used.

Answer 1

A simple (non optimal) solution is to rework l1 to keep only elements of the second list, and check equality:

def check(a, b):
    S = set(b)
    return b == [x for x in a if x in S]

check(l1, l3)

Test:

for l in [l2, l3, l4, l5, l6]:
    print(check(l1, l))

Output:

False
True
True
False
False

Answer 2

Try this:

def is_subsequence(list1, list2):
    return set(list2) <= set(list1) and list2 == sorted(list2, key=list1.index)

Not the most optimal method, but it basically sorts the smaller list using the indices of the main list and checks if the elements are still in the same positions:

print(is_subsequence(l1, [2, 1]))           # False
print(is_subsequence(l1, [1, 2, 4]))        # True
print(is_subsequence(l1, [2, 3]))           # True
print(is_subsequence(l1, [2, 3, 1]))        # False
print(is_subsequence(l1, [1, 2, 3, 4, 5]))  # False

Answer 3

Here is an efficient solution. For each element in the second list, get the next element of the first one until you have a match. If you reach the end of the first list before you matched all, this is False else True

def check(a, b):
    i = iter(a)
    return all(e in i for e in b)

Or manual version:

def check(a, b):
    i = iter(a)
    for e in b:
        try: 
            while e != next(i):
                pass
        except StopIteration:
            return False
    return True

Test:

for l in [l2, l3, l4, l5, l6]:
    print(check(l1, l))

Output:

False
True
True
False
False