Esta es una generalización de la «cadena contiene la subcadena» problema (mas) tipo arbitrario.

Dada una secuencia (como una lista o tupla), ¿cuál es la mejor manera de determinar si la otra secuencia es dentro de ella? Como un bono, debe devolver el índice del elemento donde la larga se inicia:

Ejemplo de uso (la 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, acabo de confiar en la fuerza bruta y parece lento, feo y torpe.

InformationsquelleAutor Gregg Lind | 2009-01-08

9 Comentarios

  1. 20

    La segunda la Knuth-Morris-Pratt algoritmo. Por el camino, su problema (y el KMP solución) es exactamente la receta 5.13 en Python Libro De Cocina 2ª edición. Usted puede encontrar el código relacionado a http://code.activestate.com/recipes/117214/

    Encuentra todos la correcta subsecuencias en una secuencia determinada, y debe ser usado 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)
    • Tenga en cuenta que el KMP implementación dada en el código.activestate fue demostrably más lento por 30-500 veces para algunos (tal vez no representativo de la entrada). La evaluación comparativa para ver si tonto métodos integrados de superar a la que parece ser una buena idea!
    • KMP es conocido alrededor de dos veces tan lento como el ingenuo algoritmo en la práctica. Por lo tanto, para la mayoría de los propósitos es completo inadecuado, a pesar de su buena asintótica del peor caso de tiempo de ejecución.
  2. 9

    Aquí es un ataque de fuerza bruta enfoque O(n*m) (similar a @mcella la respuesta). Podría ser más rápido que el de Knuth-Morris-Pratt implementación del algoritmo en Python puro O(n+m) (ver @Gregg Lind respuesta) para pequeño 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 la pequeño en este caso?

  3. 3

    Un enfoque simple: Convertir a cuerdas y dependen de la cadena coincidente.

    Ejemplo el uso de listas de cadenas:

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

    Ejemplo de uso de tuplas de cadenas:

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

    Ejemplo el uso de 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
    • Me gusta! Para un rápido & cosas sucias, de todos modos. En general: def is_in(seq1, seq2): return str(list(seq1))[1:-1] in str(list(seq2))[1:-1] No es una buena manera para encontrar el índice del partido, supongo.
  4. 2
    >>> 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 algoritmo de expertos, es sólo la forma más rápida de las cosas que mi mente puede pensar en el momento en que, al menos creo que se ve bien (para mí) y me he divertido de codificación de la misma. 😉

    Más probablemente es la misma cosa que su fuerza bruta enfoque está haciendo.

    • Es agradable un limpio, pero bruta forcy –> O(mn)
  5. 1

    Fuerza bruta puede estar bien para los pequeños patrones.

    Para los mayores, mirar el Algoritmo de Aho-Corasick.

    • Aho-Corasick sería genial. Estoy buscando específicamente para python, o pythonish soluciones… así que si hay una aplicación, que sería genial. Voy a hurgar.
  6. 1

    Aquí es otro KMP aplicación:

    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
    • El tee llamadas no parecen ser buenos para nada desde el otro elemento en el tee de salida 2-tupla es ignorado. seq1 y seq2 son cada copia a dos nuevos generadores, uno de los cuales obtiene instanciado en una lista, y el otro del que se ignora.
  7. 0

    Estoy un poco tarde a la fiesta, pero aquí es algo simple, utilizando 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ñaló Ilya V. Schurov, el encontrar método en este caso no se devolverá el correcto índices con múltiples cadenas de caracteres o números de varios dígitos.

    • Esta solución no es fiable en el caso de los elementos de las secuencias tienen no únicos lenghs: convertirse no es obvio cómo traducir índice devuelve el índice en secuencias iniciales. Tenga en cuenta también que el acento grave para `d` sintaxis es obsoleto como para Python 3 y desanimados.
    • ejemplo de la no fiabilidad, incluso con todos los mismos tamaños : sub=’ab’, completa=’aa’, bb’
  8. -1

    Otro enfoque, el uso de conjuntos:

    set([5,6])== set([5,6])&set([4,'a',3,5,6])
    True
    • Simplemente se entera de si el conjunto es un subconjunto de la secuencia. No se si es en ese orden en la secuencia. set([5,6])== set([5,6])&set([4,'a',5,4,6]) devuelve True
    • que podría ser una primera prueba rápida sin embargo : comprobar que todos los elementos están en la lista completa.

Dejar respuesta

Please enter your comment!
Please enter your name here