tamaño - metodos de listas en python

Probando si una lista contiene otra lista con Python

Question

¿Cómo puedo probar si una lista contiene otra lista (es decir, es una subsecuencia contigua)? Supongamos que hay una función llamada contains:

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 respuesta. 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`

Answer 2

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 pitónico, 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 la cláusula else en la declaración for ; 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 así como el algoritmo Boyer-Moore .

Answer 3

Aquí hay un algoritmo sencillo que usa métodos de lista:

#!/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 4

Código más pequeño:

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

Answer 5

Creo que este 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 6

Después de la 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 7

Esto funciona y es bastante rápido ya que realiza la búsqueda lineal utilizando el método list.index() 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 8

Hay una función all() y any() para hacer esto. Para verificar si list1 contiene TODOS los elementos en list2

result = all(elem in list1 for elem in list2)

Para verificar si list1 contiene CUALQUIER elemento en list2

result = any(elem in list1 for elem in list2)

el resultado de la variable sería booleano (VERDADERO / FALSO).

Answer 9

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

Answer 10

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

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 usé para ajustar este one-liner:

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

Answer 11

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

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

Answer 12

Traté de hacer esto lo más eficiente posible.

Utiliza un generador; a los que no están familiarizados con estas bestias se les aconseja que revisen su documentación y la de las expresiones de rendimiento .

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 del sub .

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

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

Dado que funciona para cualquier secuencia, incluso puede usarla en cadenas, en cuyo caso se comporta de manera similar a str.find , excepto que devuelve False 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 esto pretende ser una rutina de propósito general o si 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