I'd be surprised if this hasn't been asked yet.
Let's say I have an array [5,6,7,29,34]
and I want to check if the sequence 5,6,7
appears in it (which it does). Order does matter.
How would I do this?
Just for fun, here is a quick (very quick) and dirty (very dirty) solution (that is somewhat flawed, so don't really use this):
>>> str([5,6,7]).strip('[]') in str([5,6,7,29,34])
True
The RightWay™ is likely to use list.index() to find candidate matches for the first element and then verify the full match with slicing and list equality:
>>> def issubsequence(sub, seq):
i = -1
while True:
try:
i = seq.index(sub[0], i+1) # locate first character
except ValueError:
return False
if seq[i : i+len(sub)] == sub: # verify full match
return True
>>> issubsequence([5, 6, 7], [5,6,7,29,34])
True
>>> issubsequence([5, 20, 7], [5,6,7,29,34])
False
Edit: The OP clarified in a comment that the subsequence must be in order but need not be in consecutive positions. That has a different and much more complicated solution which was already answered here: How do you check if one array is a subsequence of another?
True
for str([5,6,7]).strip('[]') in str([55,6,7,29,34])
.
Commented
Jul 10, 2017 at 0:06
issubsequence([1, 3], [1, 2, 3])
. It says False
instead of the correct True
.
Commented
Jul 10, 2017 at 0:17
False
as the output.
Here is a good solution:
def is_sublist(a, b):
if not a: return True
if not b: return False
return b[:len(a)] == a or is_sublist(a, b[1:])
As mentioned by Stefan Pochmann this can be rewritten as:
def is_sublist(a, b):
return b[:len(a)] == a or bool(b) and is_sublist(a, b[1:])
if not a: return True; if not b: return False
...
Commented
Jul 10, 2017 at 0:01
return b[:len(a)] == a or bool(b) and is_sublist(a, b[1:])
. Your two ifs don't really help.
Commented
Jul 10, 2017 at 0:10
Here's a solution that works (efficiently!) on any pair of iterable objects:
import collections
import itertools
def consume(iterator, n=None):
"""Advance the iterator n-steps ahead. If n is none, consume entirely."""
# Use functions that consume iterators at C speed.
if n is None:
# feed the entire iterator into a zero-length deque
collections.deque(iterator, maxlen=0)
else:
# advance to the empty slice starting at position n
next(islice(iterator, n, n), None)
def is_slice(seq, subseq):
"""Returns whether subseq is a contiguous subsequence of seq."""
subseq = tuple(subseq) # len(subseq) is needed so we make it a tuple.
seq_window = itertools.tee(seq, n=len(subseq))
for steps, it in enumerate(seq_window):
# advance each iterator to point to subsequent values in seq.
consume(it, n=steps)
return any(subseq == seq_slice for seq_slice in izip(*seq_window))
consume
comes from itertools recipes.
[1, 2]
matches[1, 2, 3, 4]
but not[3, 2, 1, 4]
.[5,7,29]
a "subarray" of[5,6,7,29,34]
? It is a subsequence.