Prueba si una lista contiene otra lista con Python

Question

¿Cómo puedo comprobar si una lista contiene otra lista (es decir, es una subsecuencia). Decir que no hubo una función llamada contiene:

contains([1,2], [-1, 0, 1, 2]) # Returns [2, 3] (contains returns [start, end]) 
contains([1,3], [-1, 0, 1, 2]) # Returns False 
contains([1, 2], [[1, 2], 3) # Returns False 
contains([[1, 2]], [[1, 2], 3]) # Returns [0, 0] 

Editar:

contains([2, 1], [-1, 0, 1, 2]) # Returns False 
contains([-1, 1, 2], [-1, 0, 1, 2]) # Returns False 
contains([0, 1, 2], [-1, 0, 1, 2]) # Returns [1, 3] 

Answer 1

Aquí está mi versión:

def contains(small, big): 
    for i in xrange(len(big)-len(small)+1): 
     for j in xrange(len(small)): 
      if big[i+j] != small[j]: 
       break 
     else: 
      return i, i+len(small) 
    return False 

Devuelve una tupla de (inicio, final + 1) ya que creo que es más Pythonic, como señala Andrew Jaffe en su comentario. No corta ninguna sublista, por lo que debe ser razonablemente eficiente.

Un punto de interés para los novatos es que usa el else clause on the for statement - esto no es algo que use muy a menudo, pero puede ser muy valioso en situaciones como esta.

Esto es idéntico a buscar subcadenas en una cadena, por lo que para listas grandes puede ser más eficiente implementar algo como el Boyer-Moore algorithm.

Answer 2

Si todos los elementos son únicos, se puede usar conjuntos.

>>> items = set([-1, 0, 1, 2]) 
>>> set([1, 2]).issubset(items) 
True 
>>> set([1, 3]).issubset(items) 
False 

Answer 3

Después de edición de OP:

def contains(small, big): 
    for i in xrange(1 + len(big) - len(small)): 
     if small == big[i:i+len(small)]: 
      return i, i + len(small) - 1 
    return False 

Answer 4

Esto funciona y es bastante rápido como lo hace la búsqueda lineal utilizando el método de list.index() orden interna y == operador:

def contains(sub, pri): 
    M, N = len(pri), len(sub) 
    i, LAST = 0, M-N+1 
    while True: 
     try: 
      found = pri.index(sub[0], i, LAST) # find first elem in sub 
     except ValueError: 
      return False 
     if pri[found:found+N] == sub: 
      return [found, found+N-1] 
     else: 
      i = found+1 

Answer 5

Traté de hacerlo lo más eficiente posible.

Utiliza un generador; Aquellos que no estén familiarizados con estas bestias deben consultar their documentation y yield expressions.

Básicamente crea un generador de valores de la subsecuencia que se puede restablecer enviándole un valor verdadero. Si el generador se reinicia, comienza a ceder nuevamente desde el comienzo de sub.

Luego compara los valores sucesivos de sequence con los rendimientos del generador, restableciendo el generador si no coinciden.

Cuando el generador se queda sin valores, es decir, llega al final de sub sin reiniciar, eso significa que hemos encontrado nuestra coincidencia.

ya que funciona para cualquier secuencia, incluso se puede utilizar en cadenas, en cuyo caso se comporta de manera similar a str.find, excepto que devuelve False en lugar de -1.

Como nota adicional: creo que el segundo valor de la tupla devuelta debería, de acuerdo con los estándares de Python, normalmente ser uno más alto. es decir, "string"[0:2] == "st". Pero la especificación dice lo contrario, así es como funciona esto.

Depende de si se trata de una rutina de propósito general o si se está implementando algún objetivo específico; en el último caso, podría ser mejor implementar una rutina de propósito general y luego envolverla en una función que modifique el valor de retorno para adaptarlo a la especificación.

def reiterator(sub): 
    """Yield elements of a sequence, resetting if sent ``True``.""" 
    it = iter(sub) 
    while True: 
     if (yield it.next()): 
      it = iter(sub) 

def find_in_sequence(sub, sequence): 
    """Find a subsequence in a sequence. 

    >>> find_in_sequence([2, 1], [-1, 0, 1, 2]) 
    False 
    >>> find_in_sequence([-1, 1, 2], [-1, 0, 1, 2]) 
    False 
    >>> find_in_sequence([0, 1, 2], [-1, 0, 1, 2]) 
    (1, 3) 
    >>> find_in_sequence("subsequence", 
    ...     "This sequence contains a subsequence.") 
    (25, 35) 
    >>> find_in_sequence("subsequence", "This one doesn't.") 
    False 

    """ 
    start = None 
    sub_items = reiterator(sub) 
    sub_item = sub_items.next() 
    for index, item in enumerate(sequence): 
     if item == sub_item: 
      if start is None: start = index 
     else: 
      start = None 
     try: 
      sub_item = sub_items.send(start is None) 
     except StopIteration: 
      # If the subsequence is depleted, we win! 
      return (start, index) 
    return False 

Answer 6

Aquí está un sencillo algoritmo que utiliza métodos de listas:

#!/usr/bin/env python 

def list_find(what, where): 
    """Find `what` list in the `where` list. 

    Return index in `where` where `what` starts 
    or -1 if no such index. 

    >>> f = list_find 
    >>> f([2, 1], [-1, 0, 1, 2]) 
    -1 
    >>> f([-1, 1, 2], [-1, 0, 1, 2]) 
    -1 
    >>> f([0, 1, 2], [-1, 0, 1, 2]) 
    1 
    >>> f([1,2], [-1, 0, 1, 2]) 
    2 
    >>> f([1,3], [-1, 0, 1, 2]) 
    -1 
    >>> f([1, 2], [[1, 2], 3]) 
    -1 
    >>> f([[1, 2]], [[1, 2], 3]) 
    0 
    """ 
    if not what: # empty list is always found 
     return 0 
    try: 
     index = 0 
     while True: 
      index = where.index(what[0], index) 
      if where[index:index+len(what)] == what: 
       return index # found 
      index += 1 # try next position 
    except ValueError: 
     return -1 # not found 

def contains(what, where): 
    """Return [start, end+1] if found else empty list.""" 
    i = list_find(what, where) 
    return [i, i + len(what)] if i >= 0 else [] #NOTE: bool([]) == False 

if __name__=="__main__": 
    import doctest; doctest.testmod() 

Answer 7

Creo que éste es rápido ...

def issublist(subList, myList, start=0): 
    if not subList: return 0 
    lenList, lensubList = len(myList), len(subList) 
    try: 
     while lenList - start >= lensubList: 
      start = myList.index(subList[0], start) 
      for i in xrange(lensubList): 
       if myList[start+i] != subList[i]: 
        break 
      else: 
       return start, start + lensubList - 1 
      start += 1 
     return False 
    except: 
     return False 

Answer 8

¿Puedo sugerir humildemente la Rabin-Karp algorithm si la lista es big realmente grande. El enlace incluso contiene código casi utilizable en casi-Python.

Answer 9

Si refinamos el problema hablando de las pruebas si una lista contiene otra lista con como una secuencia, la respuesta podría ser el siguiente de una sola línea:

def contains(subseq, inseq): 
    return any(inseq[pos:pos + len(subseq)] == subseq for pos in range(0, len(inseq) - len(subseq) + 1)) 

Aquí pruebas unitarias que utilizar para ajustar éste -liner:

https://gist.github.com/anonymous/6910a85b4978daee137f

Answer 10

código más pequeño:

def contains(a,b): 
    str(a)[1:-1].find(str(b)[1:-1])>=0 

Answer 11

Aquí está mi solución. Esta función lo ayudará a averiguar si B es una sub-lista de A. La complejidad del tiempo es O (n).

def does_A_contain_B(A, B): #remember now A is the larger list b_size = len(B) for a_index in range(0, len(A)): if A[a_index : a_index+b_size]==B: return True else: return False