How to find if a list is a subset of another list in order? [closed]

Question

I know how to find whether a list is a subset of another list. But I was wondering how do you make sure that a list is an ordered subset of another list. By ordered subset I mean that the elements in both the list are in same order

For example if I have the following lists

A = [1,2,3]
B = [1,2]
C = [2,1]

Here B is an ordered subset of A but C is not (although A has all elements of C)

Answer 1

Use a simple loop to iterate through both lists in order. At the end, check if all elements of the potential subset list have been seen.

i,j = 0,0
while i < len(A) and j < len(B):
    if A[i] == B[j]:
        j += 1
    i += 1

has_as_subset = (j == len(B))

Answer 2

def is_sub(sub, lst):
    ln = len(sub)
    for i in range(len(lst) - ln + 1):
        if all(sub[j] == lst[i+j] for j in range(ln)):
            return True
    return False

Output:

In [21]: A = [4, 3, 2, 1, 2, 3]

In [22]: B = [1, 2]

In [23]: C = [2, 1]

In [24]: is_sub(B, A)
Out[24]: True

In [25]: is_sub(C, A)
Out[25]: True
In [26]: B = [10,11,12,13,14,15,25]
In [27]: is_sub(B, A)
Out[27]: False
In [39]: A = [1, 2, 1, 2, 1, 2, 3]
In [40]: B = [1, 2, 3]

In [41]: is_sub(B, A)
Out[41]: True

We don't need to worry about the sub being longer than lst as is it is stop will be less that start so we just return False.

You can combine it with any:

def is_sub(s, l):
    ln = len(s)
    return any((all(s[j] == l[i + j] for j in range(ln))
                for i in range(len(l) - ln + 1)))

Depending on your use case slicing might be faster:

def is_sub(sub, lst):
    ln = len(sub)
    return any(lst[i: i + ln] == sub for i in range(len(sub) - ln + 1))

If the elements can have gaps then it is a lot simpler, similar to kfx's you can do it in a single pass or less:

def is_sub_with_gap(sub, lst):
    ln, j = len(sub), 0
    for ele in lst:
        if ele == sub[j]:
            j += 1
        if j == ln:
            return True
    return False

The fundamental difference being what you consider a subset:

In [6]: a,b = [1,2,3,4], [1,2,4]

In [7]: is_sub(b,a)
Out[7]: False

In [8]: is_sub_with_gap(b,a)
Out[8]: True