3

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?

14
  • 2
    Like substring or like subsequence? Commented Jul 9, 2017 at 23:59
  • I assume order matters? eg. [1, 2] matches [1, 2, 3, 4] but not [3, 2, 1, 4].
    – Chris
    Commented Jul 9, 2017 at 23:59
  • @ChristianDean yes, order matters.
    – Graviton
    Commented Jul 10, 2017 at 0:00
  • 1
    Do you consider [5,7,29] a "subarray" of [5,6,7,29,34]? It is a subsequence. Commented Jul 10, 2017 at 0:08
  • 1
    @RaymondHettinger You don't know the difference between substring and subsequence? I'm surprised. Commented Jul 10, 2017 at 0:23

3 Answers 3

4

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?

8
  • 2
    Meh, that also says True for str([5,6,7]).strip('[]') in str([55,6,7,29,34]). Commented Jul 10, 2017 at 0:06
  • And your added solution fails issubsequence([1, 3], [1, 2, 3]). It says False instead of the correct True. Commented Jul 10, 2017 at 0:17
  • @StefanPochmann No it doesn't. I'm getting False as the output.
    – Chris
    Commented Jul 10, 2017 at 0:18
  • @StefanPochmann The OP wants to match only subsequences that appear in the same order as the sublist. Right? That is what he told me: "@ChristianDean yes, order matters.".
    – Chris
    Commented Jul 10, 2017 at 0:19
  • 1
    @ChristianDean Yeah, apparently so many people don't know the definitions that Wikipedia's articles for substring and subsequence each right away reference the other and warn that one shouldn't confuse them :-) Commented Jul 10, 2017 at 0:45
1

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:])
4
  • 2
    "Beautiful" solution... you're so sure of yourself :) ... More seriously, you could even do if not a: return True; if not b: return False... Commented Jul 10, 2017 at 0:01
  • Perfect, you could probably lambda-ify that if one wanted to as well.
    – Graviton
    Commented Jul 10, 2017 at 0:03
  • 3
    If you're going to use this, just keep in mind that it hits the recursion limit fairly quickly. A 1000 element list is a no-go.
    – Aran-Fey
    Commented Jul 10, 2017 at 0:04
  • Could just do 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
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.