確定迭代器是否包含某個特定序列，是否有內建的Python？

Question

例如，像：

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

我知道in運營商可以爲字符串做到這一點：

>>> "12" in "123" 
True 

但我正在尋找的東西，在iterables工作。

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

你可以將它轉換成字符串，然後你就知道它

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

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 - 但是您可以擺脫切片的好處。您可以重新編寫它來一次檢查一個元素，而不是使用切片，但我有一種感覺，性能會受到更多影響。

Answer 4

有沒有Python內建？不可以。您可以通過各種方式完成此任務。 Here is a recipe，做它，也給你的子序列的包含序列中的位置：

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 5

正如其他人所說，這裏沒有內建的。這裏的一個實現可能比我見過的其他答案更有效 - 特別是，它通過迭代器掃描，只是跟蹤它所看到的目標序列的前綴大小。但是，提高效率需要花費一些代價，以提高其他一些方法的冗長度。

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 6

如果保序是沒有必要的，可以用組（內置）：

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

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 

注意，這兩個參數均接受任意iterables（不需要切片）。