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
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.
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
hpos in the recursive call -- you will get false positives with repeated values in the needle but not the haystack.This scans the lists and is a different 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 the subset of list 2 (between p2 and the end) for it. If it is found, it restricts the range following searches by updating p2. If it is not found, False is returned. True is returned if every element in lst1 is found.
element_found, and only call len once outside the loops. I've edited your answer to show this. I've also posted two different takes on this method in my answer.