Establish if a continuous sequence exists within tuple

Question

I wish to establish if a continuous sequence exists within a tuple.

For example, I wish to return True in this case:

is_sequence_within((1,2), (1,2,3))

and False in this case:

is_sequence_within((1,3), (1,2,3))

I wouldn't use the word "subset" here; there are no sets, and `{1,3}.issubset({1,2,3})` gives `True`. Do you mean "contiguous subsequence"? — DSM, Feb 23 '14 at 18:32
It's not a subset. It's finding if one sequence of elements is contained in the other. — Wookie88, Feb 23 '14 at 18:35
@Lutz Horn I don't intend on reinventing the wheel if such a function is already available within a library. — Baz, Feb 23 '14 at 18:38

score 2 · Answer 1 · answered Feb 23 '14 at 18:38

I feel like this is something that itertools will handle more elegantly, but....

def is_sequence_within(seq, target):
    for i in range(len(target)-len(seq)+1):
        if seq == target[i:i+len(seq)]: return True
    return False

Alternatively:

def is_sequence_within(seq, target):
    return any(seq==target[i:i+len(seq)] for i in range(len(target)+1-len(seq)))

score 2 · Answer 2 · answered Feb 23 '14 at 18:38

You can try the following:

def is_subset(key, tup):
    for i in range(len(tup) - len(key) + 1):
        if key == tup[i : i + l]:
            return True
    return False

Or in a shorter way:

def is_subset(key, tup):
    return any(key == tup[i:i + len(key)] for i in range(len(tup) - len(key) + 1))

Output:

print is_subset((1, 2), (1, 2, 3)) # True
print is_subset((1, 3), (1, 2, 3)) # False

score 1 · Answer 3 · answered Feb 23 '14 at 18:39

A simple trick would be to rely on substring search (that is quite optimized in Python)

def is_sequence_within(needle, haystack):
    if len(needle) == 0:
        return True
    return ("," + ",".join(map(str, needle)) + "," in
            "," + ",".join(map(str, haystack)) + ",")

if this is doable and/or efficient or not depends on how big are the tuples and what is the content.

Of course if you also search the same sequence for many subsequences then caching the haystack string would be much better.

Establish if a continuous sequence exists within tuple

3 Answers3