在列表中查找连续值

Question

我有一组数值：

a = [1,3,4,5,2]

现在我想要一个这样的功能：

does_segment_exist(a, [1,3,4]) #True
does_segment_exist(a, [3,4,5]) #True
does_segment_exist(a, [4,5,2]) #True
does_segment_exist(a, [1,4,5]) #False
does_segment_exist(a, [1,3]) #True
does_segment_exist(a, [1,4]) #False

也就是说，这些数值必须是连续出现的。

有没有什么聪明的方法可以在Python 3中实现这个功能？

Answer 1

有很多方法可以做到这一点，它们都和子串搜索算法是一样的。

最简单的方法就是用简单的搜索，利用列表的index()函数找到一个共同的起点，然后用切片来检查是否完全匹配。如果没有匹配，就继续搜索，直到找到列表的末尾。

Answer 2

这个代码应该在Python 2.5及更新版本中可以正常运行：

def does_segment_exist(sequence, segment):
    n, m = len(sequence), len(segment)
    return any(segment == sequence[i:i+m] for i in range(n+1-m))

Answer 3

你可以使用一个滚动窗口的迭代器，这里提到的是来自旧版的 itertools 文档的一个例子：

from itertools import islice

def window(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))
    if len(result) == n:
        yield result
    for elem in it:
        result = result[1:] + (elem,)
        yield result

def does_segment_exist(iterable, sublist):
    return tuple(sublist) in window(iterable, len(sublist))

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

如果你只需要它在列表上工作，而不是任何可迭代的对象，你可以使用：

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))

这是Raymond提到的方法的一个基本实现：

def does_segment_exist(seq, sublist):
    first = sublist[0]
    i = 0
    n = len(sublist)
    while True:
        try:
            i = seq.index(first, i)
        except ValueError:
            return False
        if sublist == seq[i:i+n]:
            return True
        i += 1

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

这个方法的好处在于，它不需要对每个索引进行切片，直到找到第一个匹配项，而只需对与段中第一个值对应的匹配项的索引进行切片。