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?

Raymond Hettinger
  • 216,523
  • 63
  • 388
  • 485
Graviton
  • 371
  • 1
  • 4
  • 14
  • 2
    Like substring or like subsequence? – Stefan Pochmann Jul 09 '17 at 23:59
  • I assume order matters? eg. `[1, 2]` matches `[1, 2, 3, 4]` but not `[3, 2, 1, 4]`. – Christian Dean Jul 09 '17 at 23:59
  • @ChristianDean yes, order matters. – Graviton Jul 10 '17 at 00:00
  • @StefanPochmann Subsequence? Though I'm not entirely sure what the difference is. – Graviton Jul 10 '17 at 00:04
  • 1
    Do you consider `[5,7,29]` a "subarray" of `[5,6,7,29,34]`? It **is** a subsequence. – Stefan Pochmann Jul 10 '17 at 00:08
  • @StefanPochmann Right, that makes more sense – Graviton Jul 10 '17 at 00:09
  • Ok but then you shouldn't call pythad's solution "perfect", since that only detects substring-like subarrays. – Stefan Pochmann Jul 10 '17 at 00:13
  • 1
    @RaymondHettinger **You** don't know the difference between substring and subsequence? I'm surprised. – Stefan Pochmann Jul 10 '17 at 00:23
  • @StefanPochmann That "duplicate" question relates no answer to this question. Order and consecutive elements matters in this one, while the other does not. – Graviton Jul 10 '17 at 01:05
  • @Graviton Sounds like you're confused. The answers there do work for your question. Why are you saying now that "consecutive elements matters"? Earlier you clearly confirmed that it doesn't. – Stefan Pochmann Jul 10 '17 at 01:22
  • @StefanPochmann My bad, must have misread the question. – Graviton Jul 10 '17 at 01:23
  • @Graviton I see you actually changed the question now. Or rather attempted to. Because right now it contradicts itself, as `[5,6,7]` **is** a subsequence of `[5,6,4,7]`, so the answer should be `True`. Anyway, questions shouldn't be changed like that. – Stefan Pochmann Jul 10 '17 at 01:42
  • @StefanPochmann I thought so, what terminology would fix that? – Graviton Jul 10 '17 at 01:42
  • Read my very first comment again and have a guess. But again, questions shouldn't be changed like that. You made it absolutely clear that you're talking about subsequences (since I gave you an example with a non-continuous subsequence and you acknowledged it and then you renamed your question to say subsequence). Changing it away from subsequence would invalidate a correct answer. That's not cool. – Stefan Pochmann Jul 10 '17 at 01:46

3 Answers3

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?

Raymond Hettinger
  • 216,523
  • 63
  • 388
  • 485
  • 2
    Meh, that also says `True` for `str([5,6,7]).strip('[]') in str([55,6,7,29,34])`. – Stefan Pochmann Jul 10 '17 at 00:06
  • And your added solution fails `issubsequence([1, 3], [1, 2, 3])`. It says `False` instead of the correct `True`. – Stefan Pochmann Jul 10 '17 at 00:17
  • @StefanPochmann No it doesn't. I'm getting `False` as the output. – Christian Dean Jul 10 '17 at 00: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."_. – Christian Dean Jul 10 '17 at 00:19
  • @ChristianDean Huh? It **is** the same order. Pretty sure you don't know the difference between substring and subsequence. The original question version wasn't clear about what they wanted, but since Raymond explicitly called it subsequence, it's wrong. – Stefan Pochmann Jul 10 '17 at 00:22
  • I wouldn't call a simple two-liner *"much more complicated"* :-P – Stefan Pochmann Jul 10 '17 at 00:28
  • @StefanPochmann Ah, I see what you mean. Normally when I hear someone refer to subsequence, they mean that a match must be in _consectuitve_ order. But I see now that is not the [formally definition of a subsequence](https://en.wikipedia.org/wiki/Subsequence). You're right, I didn't fully understand the difference. Thanks for helping me learn that! – Christian Dean Jul 10 '17 at 00:35
  • 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 :-) – Stefan Pochmann Jul 10 '17 at 00: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:])
pythad
  • 4,241
  • 2
  • 19
  • 41
  • 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`... – blacksite Jul 10 '17 at 00:01
  • Perfect, you could probably lambda-ify that if one wanted to as well. – Graviton Jul 10 '17 at 00: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 Jul 10 '17 at 00: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. – Stefan Pochmann Jul 10 '17 at 00: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.

Brian Rodriguez
  • 4,250
  • 1
  • 16
  • 37