How do I check if an ordered non-sequential subsequence is in an array? python
I would be surprised if this has not been asked yet.
Let's say I have an array [5,6,7,29,34]
and I want to check if a sequence appears in it 5,6,7
(what it does). The order matters.
How should I do it?
Just for fun, here's a quick (very quick) and dirty (very messy) solution (it's somewhat misleading, so don't actually use that):
>>> str([5,6,7]).strip('[]') in str([5,6,7,29,34])
True
RightWay ™ will most likely use list.index () to find candidate matches for the first element, and then check for a complete cut and equality match on the list:
>>> 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 should be in order, but not in sequential positions. This has a different and much more complex solution, which has already been answered: How do you check if one array is a subsequence of another?
Here's 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 Pohman, this can be rewritten as:
def is_sublist(a, b):
return b[:len(a)] == a or bool(b) and is_sublist(a, b[1:])
Here's a solution that works (efficiently!) On any pair of iterables:
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 .