Clever Geek Handbook

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?

+3


source to share


3 answers


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?

+4


source


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:])
+2


source


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 .

0


source






More articles:


All Articles