¿Existe un comando integrado Python para determinar si un iterable contiene una cierta secuencia?

Question

Por ejemplo, algo como:

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

sé que el operador in puede hacer esto por cadenas:

>>> "12" in "123" 
True 

Pero yo estoy buscando algo que opera en iterables.

Answer 1

referencia desde https://stackoverflow.com/a/6822773/24718 modificado para utilizar 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

podría convertir en una cadena y luego hacer juego en él

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

Por lo que yo sé, no hay manera de hacer esto. Puede ejecutar su propia función con bastante facilidad, pero dudo que sea terriblemente eficiente.

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

Tenga en cuenta que esta solución no funciona con objetos de tipo de generador (que sólo funciona en objetos que se pueden rebanar). Puede verificar seq para ver si es rebanable antes de continuar y convertirlo a un tuple si no es cortable - Pero luego se deshace de los beneficios de rebanar. Podría volver a escribirlo para verificar un elemento a la vez en lugar de usar el corte, pero tengo la sensación de que el rendimiento sufriría aún más.

Answer 4

¿Hay un built-in de Python? No. Puedes lograr esta tarea de varias maneras. Here is a recipe que lo hace, y también le da la posición de la subsecuencia de la secuencia que contiene:

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

Como han dicho otros, no hay instrucciones para esto. Aquí hay una implementación que es potencialmente más eficiente que las otras respuestas que he visto, en particular, explora el iterable, simplemente haciendo un seguimiento de los tamaños de prefijo de la secuencia de destino que se ve. Pero esa mayor eficiencia tiene algún costo en una mayor verbosidad sobre algunos de los otros enfoques que se han sugerido.

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

Si la preservación del orden no es necesario, puede utilizar conjuntos (empotrados):

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

lo 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 

Esta funciona con cualquier iterador.

Answer 7

Como no hay ninguna orden interna, hice una buena versión:

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) 

Este no requieren ninguna lista adicionales (si se utiliza o 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 

Puntos extra si no tiene problemas para leerlo. (Hace el trabajo, pero la implementación no debe tomarse demasiado en serio).;)

Answer 8

deque parece ser útil aquí:

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 

Tenga en cuenta que este acepta iterables arbitrarias para ambos argumentos (sin rebanar requerido).