How to do sub-sequence match for a simple list and a list of sets?

December 23, 2021

For example:

l1 = [1, 2, 3, 4]

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

l2 can be conceptually expanded into:

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

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

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.

The definition of a match:

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.

So one solution may be first flatten the l2 into the new l2 like above, and then the all(e in iter_of_l1 for e in sublist_l2) can be used.

The sequence from l2 is formed as: take each element from a set in l2 and put it into a list, so that you can get multiple lists. [1,3] matches [1,2,3,4] because it is a subsequence of l1.

How to do this match without explicitly expanding the l2 into a list of lists?

>Solution :

Instead of checking equality of the l1 and l2 elements, check for membership of the l1 elements in the l2 elements.

Some possible implementations (Try it online!):

it1 = iter(l1)
result = all(any(x in pool for x in it1)
             for pool in l2)

it1 = iter(l1)
result = all(not pool.isdisjoint(it1)
             for pool in l2)

it1 = iter(l1)
result = not any(pool.isdisjoint(it1)
                 for pool in l2)

from itertools import repeat
result = not any(map(set.isdisjoint, l2, repeat(iter(l1))))