Esiste un builtin Python per determinare se un iterabile contiene una determinata sequenza?

Question

Per esempio, qualcosa come:

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

so che l'operatore in può fare questo per le stringhe:

>>> "12" in "123" 
True 

ma io sono alla ricerca di qualcosa che opera su iterabili.

Answer 1

referenziato da https://stackoverflow.com/a/6822773/24718 modificati per utilizzare una lista.

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

è possibile convertire in una stringa e poi fare corrispondenza su di esso

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

Per quanto ne so, non c'è modo per fare questo. Puoi eseguire facilmente la tua funzione, ma dubito che sarà terribilmente efficiente.

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

Si noti che questa soluzione non funziona con gli oggetti di tipo generatore (funziona solo su oggetti che è possibile affettare). È possibile controllare seq per vedere se è affettabile prima di procedere e trasmettere a un tuple se non è affettabile - Ma poi si eliminano i vantaggi dell'affettatura. Potresti riscriverlo per controllare un elemento alla volta invece di usare affettare, ma ho la sensazione che le prestazioni ne soffrirebbero ancora di più.

Answer 4

C'è un builtin Python? No. Puoi svolgere questo compito in vari modi. Here is a recipe che lo fa, e ti dà anche la posizione del subsequence nella sequenza contenente:

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

Come altri hanno già detto, non c'è un built-in per questo. Ecco un'implementazione che è potenzialmente più efficiente rispetto alle altre risposte che ho visto - in particolare, analizza l'iterabile, tenendo traccia di quali dimensioni del prefisso della sequenza target è stata vista. Ma questo aumento dell'efficienza comporta alcune spese in termini di aumento della verbosità rispetto ad altri approcci suggeriti.

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

Se conservazione di ordine non è necessario, è possibile utilizzare i set (built-in):

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

In caso contrario:

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 

questo funziona con qualsiasi iteratore.

Answer 7

Poiché non c'è incorporato, ho fatto una bella versione:

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) 

Questo non richiedono ulteriori elenchi (se si utilizza it.izip o 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 

punti extra se si hanno problemi a leggerlo. (Fa il lavoro, ma l'implementazione non deve essere presa troppo sul serio).;)

Answer 8

deque sembra essere utile qui:

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 

Si noti che questo accetta iterables arbitrarie per entrambi gli argomenti (senza affettare richiesta).