Finding Consecutive Values Within A List

I have a list of values: a = [1,3,4,5,2] I now want the following function: does_segment_exist(a, [1,3,4]) #True does_segment_exist(a, [3,4,5]) #True does_segment_exist(a, [4,5,2

Solution 1:

You can use a rolling window iterator, in this case one from an old version of the itertools docs:

from itertools import islice

defwindow(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable""   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    iflen(result) == n:
        yield result
    for elem in it:
        result = result[1:] + (elem,)
        yield result

defdoes_segment_exist(iterable, sublist):
    returntuple(sublist) in window(iterable, len(sublist))

print(does_segment_exist([1,3,4,5,2], [3,4,5]))

If you only need it to work on lists, not any iterable, you can use:

def does_segment_exist(seq, sublist):
    # seq and sublist must both be lists
    n = len(sublist)
    return sublist in (seq[i:i+n]for i in range(len(seq) + 1 - n))

A basic implementation of the method mentioned by Raymond:

defdoes_segment_exist(seq, sublist):
    first = sublist[0]
    i = 0
    n = len(sublist)
    whileTrue:
        try:
            i = seq.index(first, i)
        except ValueError:
            returnFalseif sublist == seq[i:i+n]:
            returnTrue
        i += 1print(does_segment_exist([1,3,4,5,2], [3,4,5]))

The advantage of this method is that it doesn't have to slice for every index up to the first match, just for indexes corresponding to matches for the first value in the segment.

Solution 2:

There are many ways to do this and they are all isomorphic to substring search algorithms.

The easiest way is the naïve search using list.index() to find a common start point and then using a slice to check for a full match. If there is not a match, repeat the search until you hit the end of the list.

Solution 3:

This should work with Python 2.5 and newer:

defdoes_segment_exist(sequence, segment):
    n, m = len(sequence), len(segment)
    returnany(segment == sequence[i:i+m] for i inrange(n+1-m))