Comparing the order of items 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 in lst1 , but not necessarily sequentially.

For instance,

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 still have:

 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 a method using index given by Triptych. I think this is probably the best way to do this, since 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 

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

Here are two solutions that primarily repeat on top of lst2 instead of lst1 , but are otherwise similar to the jedwards version.

The first is simple and uses indexing, but only indexes, when you actually move to another element in lst1 , and not to each element 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 instead of 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 small enhancements as they reduce indexing and do not need to build a range for each element in lst1 .

Answer 2

Recursively, no decommissioned listings, new subscriptions, unsuccessful 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 

Answer 3

This is list scanning and another approach:

 def test(lst1, lst2): p2 = 0 length = len(lst2) for e1 in lst1: for p in range(p2, length): if e1 == lst2[p]: p2 = p break else: return False return True 

For each element in lst1 it searches for a subset of list 2 (between p2 and the end) for it. If found, it limits the range of the following searches by updating p2 . If it is not found, False returned. True returned if any element from lst1 .

Answer 4

 def test(lst1, lst2): for x in lst2: if x == lst1[0]: del lst1[0] return lst1 == [] 

Must work.