Reputation: 41
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
Upvotes: 4
Views: 1078
Reputation: 177000
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
.
Upvotes: 5
Reputation: 212208
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
Upvotes: 2
Reputation: 30260
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.
Upvotes: 1
Reputation: 7824
def test(lst1, lst2):
for x in lst2:
if x == lst1[0]:
del lst1[0]
return lst1 == []
Should work.
Upvotes: 0