Лучший способ определить, находится ли последовательность в другой последовательности в Python

Question

Это обобщение проблемы "строка содержит подстроку" на (более) произвольные типы.

Учитывая последовательность (например, список или кортеж), каков наилучший способ определить, находится ли внутри нее другая последовательность?В качестве бонуса он должен возвращать индекс элемента, с которого начинается подпоследовательность:

Пример использования (Последовательность в последовательности):

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

Пока я просто полагаюсь на грубую силу, и это кажется медленным, уродливым и неуклюжим.

Answer 1

Я второй алгоритм Кнута-Морриса-Пратта. Кстати, ваша проблема (и решение KMP) в точности соответствует рецепту 5.13 в Python Cookbook 2-е издание. Вы можете найти соответствующий код на http://code.activestate.com/recipes/117214/

Он находит все правильные подпоследовательности в заданной последовательности и должен использоваться как итератор:

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

Вот подход грубой силы O (n * m) (аналогично @ mcella's answer ). Это может быть быстрее, чем реализация алгоритма Кнута-Морриса-Пратта в чистом Python O (n + m) (см. @ Gregg Lind answer ) для маленьких входных последовательностей.

#!/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()

Интересно, насколько велик маленький в этом случае?

Answer 3

То же самое, что и соответствие строк, сэр ... Кнут-Моррис-Пратт соответствие строк

Answer 4

Простой подход: конвертировать в строки и полагаться на сопоставление строк.

Пример использования списков строк:

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

Пример использования кортежей строк:

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

Пример использования списков чисел:

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

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

Извините, я не эксперт по алгоритмам, это самая быстрая вещь, о которой я могу думать в данный момент, по крайней мере, я думаю, что это выглядит хорошо (для меня), и мне было весело кодировать это. ; -)

Скорее всего, это то же самое, что делает ваш метод грубой силы.

Answer 6

Грубая сила может подойти для небольших моделей.

Для более крупных взгляните на алгоритм Aho-Corasick .

Answer 7

Вот еще одна реализация 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 <neale@woozle.org>
    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 8

Я немного опоздал на вечеринку, но вот кое-что простое, использующее strings:

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

Как было отмечено Илья В.Щуров, тот самый Найти метод в этом случае не вернет правильные индексы с многозначными строками или многозначными числами.

Answer 9

Другой подход, использующий наборы:

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