tuplas - saber si un elemento esta en una lista python

La mejor forma de determinar si una secuencia está en otra secuencia en Python

Question

Esta es una generalización del problema "string contains substring" para (más) tipos arbitrarios.

Dada una secuencia (como una lista o tupla), ¿cuál es la mejor manera de determinar si hay otra secuencia dentro de ella? Como beneficio adicional, debe devolver el índice del elemento donde comienza la subsecuencia:

Ejemplo de uso (Secuencia en secuencia):

>>> seq_in_seq([5,6],  [4,''a'',3,5,6])
3
>>> seq_in_seq([5,7],  [4,''a'',3,5,6])
-1 # or None, or whatever

Hasta ahora, solo confío en la fuerza bruta y parece lento, feo y torpe.

Answer 1

Aquí hay otra implementación de KMP:

from itertools import tee

def seq_in_seq(seq1,seq2):
    ''''''
    Return the index where seq1 appears in seq2, or -1 if 
    seq1 is not in seq2, using the Knuth-Morris-Pratt algorithm

    based heavily on code by Neale Pickett <[email protected]>
    found at:  woozle.org/~neale/src/python/kmp.py

    >>> seq_in_seq(range(3),range(5))
    0
    >>> seq_in_seq(range(3)[-1:],range(5))
    2
    >>>seq_in_seq(range(6),range(5))
    -1
    ''''''
    def compute_prefix_function(p):
        m = len(p)
        pi = [0] * m
        k = 0
        for q in xrange(1, m):
            while k > 0 and p[k] != p[q]:
                k = pi[k - 1]
            if p[k] == p[q]:
                k = k + 1
            pi[q] = k
        return pi

    t,p = list(tee(seq2)[0]), list(tee(seq1)[0])
    m,n = len(p),len(t)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(n):
        while q > 0 and p[q] != t[i]:
            q = pi[q - 1]
        if p[q] == t[i]:
            q = q + 1
        if q == m:
            return i - m + 1
    return -1

Answer 2

Aquí hay un enfoque de fuerza bruta O(n*m) (similar a la respuesta de @mcella ). Puede ser más rápido que la implementación del algoritmo Knuth-Morris-Pratt en Python O(n+m) puro O(n+m) (ver @Gregg Lind answer ) para pequeñas secuencias de entrada.

#!/usr/bin/env python
def index(subseq, seq):
    """Return an index of `subseq`uence in the `seq`uence.

    Or `-1` if `subseq` is not a subsequence of the `seq`.

    The time complexity of the algorithm is O(n*m), where

        n, m = len(seq), len(subseq)

    >>> index([1,2], range(5))
    1
    >>> index(range(1, 6), range(5))
    -1
    >>> index(range(5), range(5))
    0
    >>> index([1,2], [0, 1, 0, 1, 2])
    3
    """
    i, n, m = -1, len(seq), len(subseq)
    try:
        while True:
            i = seq.index(subseq[0], i + 1, n - m + 1)
            if subseq == seq[i:i + m]:
               return i
    except ValueError:
        return -1

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

Me pregunto qué tan grande es el pequeño en este caso?

Answer 3

La fuerza bruta puede estar bien para pequeños patrones.

Para los más grandes, mira el algoritmo Aho-Corasick .

Answer 4

Llego un poco tarde a la fiesta, pero aquí hay algo simple usando cadenas:

>>> def seq_in_seq(sub, full):
...     f = ''''.join([repr(d) for d in full]).replace("''", "")
...     s = ''''.join([repr(d) for d in sub]).replace("''", "")
...     #return f.find(s) #<-- not reliable for finding indices in all cases
...     return s in f
...
>>> seq_in_seq([5,6], [4,''a'',3,5,6])
True
>>> seq_in_seq([5,7], [4,''a'',3,5,6])
False
>>> seq_in_seq([4,''abc'',33], [4,''abc'',33,5,6])
True

Como señala Ilya V. Schurov , el método de búsqueda en este caso no devolverá los índices correctos con cadenas de caracteres múltiples o números de varios dígitos.

Answer 5

Lo mismo que el juego de cordel señor ... Knuth-Morris-Pratt cordaje a juego

Answer 6

Otro enfoque, usando conjuntos:

set([5,6])== set([5,6])&set([4,''a'',3,5,6])
True

Answer 7

Secundo el algoritmo de Knuth-Morris-Pratt. Por cierto, su problema (y la solución KMP) es exactamente la receta 5.13 en Python Cookbook 2nd edition. Puede encontrar el código relacionado en http://code.activestate.com/recipes/117214/

Encuentra todas las subsecuencias correctas en una secuencia dada, y debe usarse como un iterador:

>>> for s in KnuthMorrisPratt([4,''a'',3,5,6], [5,6]): print s
3
>>> for s in KnuthMorrisPratt([4,''a'',3,5,6], [5,7]): print s
(nothing)

Answer 8

Un enfoque simple: conviértalo en cadenas y confíe en la coincidencia de cadenas.

Ejemplo usando listas de cadenas:

 >>> f = ["foo", "bar", "baz"]
 >>> g = ["foo", "bar"]
 >>> ff = str(f).strip("[]")
 >>> gg = str(g).strip("[]")
 >>> gg in ff
 True

Ejemplo usando tuplas de cadenas:

>>> x = ("foo", "bar", "baz")
>>> y = ("bar", "baz")
>>> xx = str(x).strip("()")
>>> yy = str(y).strip("()")
>>> yy in xx
True

Ejemplo usando listas de números:

>>> f = [1 , 2, 3, 4, 5, 6, 7]
>>> g = [4, 5, 6]
>>> ff = str(f).strip("[]")
>>> gg = str(g).strip("[]")
>>> gg in ff
True

Answer 9

>>> def seq_in_seq(subseq, seq):
...     while subseq[0] in seq:
...         index = seq.index(subseq[0])
...         if subseq == seq[index:index + len(subseq)]:
...             return index
...         else:
...             seq = seq[index + 1:]
...     else:
...         return -1
... 
>>> seq_in_seq([5,6], [4,''a'',3,5,6])
3
>>> seq_in_seq([5,7], [4,''a'',3,5,6])
-1

Lo siento, no soy un experto en algoritmos, es lo más rápido que mi mente puede pensar en este momento, al menos creo que se ve bien (para mí) y me divertí codificándolo. ;-)

Lo más probable es que sea lo mismo que hace tu enfoque de fuerza bruta.