python - 是否有用于确定可迭代对象是否包含某个序列的 Python 内置函数？

Question

例如，类似：

>>> [1, 2, 3].contains_sequence([1, 2])
True
>>> [1, 2, 3].contains_sequence([4])
False

我知道in操作员可以对字符串执行此操作：

>>> "12" in "123"
True

但我正在寻找对迭代进行操作的东西。

Answer 1

引用自https://stackoverflow.com/a/6822773/24718 修改为使用列表。

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

def contains_sequence(all_values, seq):
    return any(seq == current_seq for current_seq in window(all_values, len(seq)))            

test_iterable = [1,2,3]
search_sequence = [1,2]

result = contains_sequence(test_iterable, search_sequence)

Answer 2

有内置的 Python 吗？不，您可以通过多种方式完成此任务。 这是一个食谱，它还为您提供子序列在包含序列中的位置：

def _search(forward, source, target, start=0, end=None):
    """Naive search for target in source."""
    m = len(source)
    n = len(target)
    if end is None:
        end = m
    else:
        end = min(end, m)
    if n == 0 or (end-start) < n:
        # target is empty, or longer than source, so obviously can't be found.
        return None
    if forward:
        x = range(start, end-n+1)
    else:
        x = range(end-n, start-1, -1)
    for i in x:
        if source[i:i+n] == target:
            return i
    return None

Answer 3

据我所知，没有办法做到这一点。你可以很容易地滚动你自己的函数，但我怀疑这会非常有效。

>>> def contains_seq(seq,subseq):
...     #try: junk=seq[:]
...     #except: seq=tuple(seq)
...     #try: junk=subseq[:]
...     #except: subseq=tuple(subseq)
...     ll=len(subseq)
...     for i in range(len(seq)-ll):  #on python2, use xrange.
...         if(seq[i:i+ll] == subseq):
...             return True
...     return False
...
>>> contains_seq(range(10),range(3)) #True
>>> contains_seq(range(10),[2,3,6]) #False

请注意，此解决方案不适用于生成器类型的对象（它仅适用于您可以切片的对象）。您可以seq在继续之前检查它是否可切片，tuple如果它不可切片，则将其转换为 a - 但是您摆脱了切片的好处。您可以重新编写它以一次检查一个元素而不是使用切片，但我感觉性能会受到更大的影响。

Answer 4

正如其他人所说，没有内置的。这是一个可能比我见过的其他答案更有效的实现——特别是，它扫描可迭代对象，只跟踪它所看到的目标序列的前缀大小。但是，与已经提出的其他一些方法相比，这种效率的提高是以增加冗长为代价的。

def contains_seq(iterable, seq):
    """
    Returns true if the iterable contains the given sequence.
    """
    # The following clause is optional -- leave it if you want to allow `seq` to
    # be an arbitrary iterable; or remove it if `seq` will always be list-like.
    if not isinstance(seq, collections.Sequence):
        seq = tuple(seq)

    if len(seq)==0: return True # corner case

    partial_matches = []
    for elt in iterable:
        # Try extending each of the partial matches by adding the
        # next element, if it matches.
        partial_matches = [m+1 for m in partial_matches if elt == seq[m]]
        # Check if we should start a new partial match
        if elt==seq[0]:
            partial_matches.append(1)
        # Check if we have a complete match (partial_matches will always
        # be sorted from highest to lowest, since older partial matches 
        # come before newer ones).
        if partial_matches and partial_matches[0]==len(seq):
            return True
    # No match found.
    return False

Answer 5

如果不需要保留顺序，您可以使用集合（内置）：

>>> set([1,2]).issubset([1,2,3])
True
>>> set([4]).issubset([1,2,3])
False

除此以外：

def is_subsequence(sub, iterable):
    sub_pos, sub_len = 0, len(sub)
    for i in iterable:
        if i == sub[sub_pos]:
            sub_pos += 1
            if sub_pos >= sub_len:
                return True
        else:
            sub_pos = 0
    return False

>>> is_subsequence([1,2], [0,1,2,3,4])
True
>>> is_subsequence([2,1], [0,1,2,3,4]) # order preserved
False
>>> is_subsequence([1,2,4], [0,1,2,3,4])
False

这个适用于任何迭代器。

Answer 6

deque在这里似乎很有用：

from collections import deque

def contains(it, seq):
    seq = deque(seq)
    deq = deque(maxlen=len(seq))
    for p in it:
        deq.append(p)
        if deq == seq:
            return True
    return False

请注意，这接受两个参数的任意迭代（不需要切片）。

Answer 7

由于没有内置，我做了一个不错的版本：

import itertools as it

def contains(seq, sub):
    seq = iter(seq)
    o = object()
    return any(all(i==j for i,j in zip(sub, it.chain((n,),seq, 
                                      (o for i in it.count())))) for n in seq)

这不需要任何额外的列表（如果您使用it.izip或 Py3k）。

>>> contains([1,2,3], [1,2])
True
>>> contains([1,2,3], [1,2,3])
True
>>> contains([1,2,3], [2,3])
True
>>> contains([1,2,3], [2,3,4])
False

如果您阅读没有问题，可以加分。（它可以完成这项工作，但不要太认真地对待实施）。;)

Answer 8

您可以将其转换为字符串，然后对其进行匹配

full_list = " ".join([str(x) for x in [1, 2, 3]])
seq = " ".join([str(x) for x in [1, 2]])
seq in full_list