Comparing element order in Python lists

Question

I am trying to write a function that returns True if the elements in lst1 appear in lst2 in the same order as they appear in lst1, but not necessarily consecutively.

For example,

test([29, 5, 100], [20, 29, 30, 50, 5, 100]) should return True.

test([25, 65, 40], [40, 25, 30, 65, 1, 100]) should return False.

Here is what I have so far:

def test(lst1, lst2):
    for i in range(len(lst1)-len(lst2)+1):
        if lst2 == lst1[i:i+len(lst2)]:
            return True 
    return False 

Answer 1

Here is an iterative version of the method using index given by Triptych. I think this is probably the best way to do this, as index should be faster than any manual indexing or iteration:

def test(lst1, lst2):
    start = 0
    try:
        for item in lst1:
            start = lst2.index(item, start) + 1
    except ValueError:
        return False
    return True

It should perform much better in Python than a recursive version. It also correctly adds one to the start point after each search so as not to give false positives when there are duplicates in the first list.

Here are two solutions that iterate primarily over lst2 instead of lst1, but are otherwise similar to jedwards' version.

The first is straightforward, and uses indexing, but only indexes when you actually move to a different item in lst1, rather than for every item in lst2:

def test(lst1, lst2):
    length, i, item = len(lst1), 0, lst1[0]
    for x in lst2:
        if x == item:
            i += 1
            if i == length:
                return True
            item = lst1[i]
    return False

The second uses manual iteration over lst1 with next rather than indexing:

def test(lst1, lst2):
    it = iter(lst1)
    try:
        i = next(it)
        for x in lst2:
            if x == i:
                i = next(it)
    except StopIteration:
        return True
    return False

Both are probably slight improvements as they do less indexing and have no need to construct a range for every item in lst1.

Answer 2

Recursively, no clobbered lists, no new sublists, failing early

def find_all(needle, haystack, npos=0, hpos=0):
  if npos >= len(needle):
    return True
  try:
    return find_all(needle, haystack, npos+1, haystack.index(needle[npos], hpos)+1) 
  except ValueError:
    return False


print find_all([1,3,5], [1,2,3,4,5,6,7]) # True
print find_all([1,5,3], [1,2,3,4,5,6,7]) # False