Python中有没有内置函数可以确定可迭代对象是否包含特定序列？

Question

例如，像这样的东西：

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

我知道in运算符可以用于字符串：

>>> "12" in "123"
True

但我需要的是能够处理可迭代对象的东西。

- David Wolever

---

序列是否可以出现在另一个序列的任何位置？ - Jon Clements

确定正确性 - 两个序列都不是可迭代对象？ - Jon Clements

这个“haystack”是可迭代的，但是要求“needle”也是可迭代的没有意义（据我所知，它必须被展开）。 - David Wolever

是的，但我遇到过一些疯狂的客户 :) 比如，“明天之前你肯定可以改变我们有200百万行的57个表格数据库” :) - Jon Clements

好的，我刚刚意识到已经过了凌晨5点了，需要稍微准备一下去上班了，但我整晚都在电脑前 :(所以如果你没有得到一个令人满意的答案，它会一直萦绕在我的脑海中，但是如果有的话，我很期待看到它。祝好运！ - Jon Clements

Answer 1

参考自https://dev59.com/iGw15IYBdhLWcg3wG4AJ#6822773，修改为使用列表。

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)

- monkut

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

- BrenBarn

---

感谢您在给出实现之前回答了实际问题（“是否有内置”）。 - David Wolever

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 - 但这样会丢失切片的好处。您可以重新编写它以逐个检查一个元素，而不是使用切片，但我觉得性能会更差。

- mgilson

---

@mgilson: 你是不是想说"在 Python 2 中，使用 xrange"？ - Junuxx

@EdwardLoper -- 这是真的。 我其实也想过了。 严格来讲，我会认为xrange是一个iterable 而不是一个sequence( http://docs.python.org/glossary.html )。就个人而言，出于我上面提到的原因，我认为该函数应该仅支持sequences。 - mgilson

@mgilson 这个问题的标题明确指定我们应该在可迭代对象中搜索，并且David在问题的评论中重申了这一点：“干草堆是一个可迭代对象，但没有必要要求针是一个可迭代对象。” - Edward Loper

@mgilson 是的，仅支持列表确实更简单并且（至少可能）更快。然而，考虑到我需要操作可迭代对象，这也是不正确的 =\ - David Wolever

@DavidWolever -- 这不仅适用于列表，也适用于元组、字符串和任何可以切片的东西。我添加了try/except子句，使其可以与其他东西一起使用（通过将它们转换为元组）。 - mgilson

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

- Edward Loper

---

我不觉得我会使用hasattr。虽然你可以检查sets和一些用户定义的对象，但我通常不会期望不支持__getitem__的对象是有序的。我认为更好的方法是强制用户显式地转换为另一个对象--虽然我想它确实允许使用生成器等(但抛弃了它们的所有好处)... - mgilson

加入 hasattr 一段是为了允许 seq (即 "needle") 可以是任意的可迭代对象，如果需要的话 -- 比如 contains_seq(xrange(100), xrange(3,8))。如果已知 needle 是类似于列表的对象，那么可以省略掉这个检查。 - Edward Loper

hasattr检查最好改写为：if not isinstance(seq, collections.Sequence)（尽管这样会有稍微不同的语义，所以你可能还想检查collections.Mapping）。而且它应该放在对空序列的检查之前。 - lvc

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

这个可以适用于任何迭代器。

- Aleksei astynax Pirogov

---

@mgilson，感谢您的评论！另一种变体已被添加 - 它适用于可迭代对象并保留子序列的顺序。 - Aleksei astynax Pirogov

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

请注意，此函数接受任意可迭代对象作为两个参数（无需切片）。

- georg

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

如果您能轻松阅读它，那就更好了。（它可以完成工作，但实现不应该被过分认真对待）。;)

- JBernardo

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

- Yunchi

---

只有当这些项目可以合理地转换为字符串时，才能正常工作。 - David Wolever

是的，但所给出的示例是针对整数的，这可以很容易地转换为字符串。不仅如此，使用str.join然后再使用in运算符是一种非常高效的方法，因为与迭代列表相比，str.join是一种高效的操作。 - Yunchi

对于输入 ['list','one','list','two']，在寻找 ['list one','list two'] 时也会返回 True。虽然这是一个罕见的情况，但还是值得一提的。 - mgilson

是的，但这个例子只是一个例子。标题和最后一段都清楚地表明我对通用可迭代对象感兴趣。此外，您提出的方法是不正确的，即使输入仅为整数：考虑我想确定[12]是否包含序列[1]（或确定["foobar"]是否包含["foo"]）的情况。 - David Wolever

啊，那是真的，我没有考虑到任何这些情况。 - Yunchi