Тестирование, если список содержит другой список с Python

Ответ 1

Вот моя версия:

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

Он возвращает кортеж (start, end + 1), поскольку я думаю, что это более pythonic, как указывает Andrew Jaffe в своем комментарии. Он не разрезает никаких подписок, поэтому должен быть достаточно эффективным.

Одна из интереснейших новинок заключается в том, что она использует предложение else в инструкции for - это не то, что я использую очень часто, но могу быть неоценимым в таких ситуациях.

Это идентично поиску подстрок в строке, поэтому для больших списков может быть более эффективным реализовать что-то вроде алгоритма Boyer-Moore.

Ответ 2

Если все элементы уникальны, вы можете использовать наборы.

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

Ответ 3

После редактирования 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

Ответ 4

Могу ли я смиренно предложить алгоритм Рабина-Карпа, если список big действительно большой. Ссылка даже содержит почти полезный код в почти-Python.

Ответ 5

Это работает и довольно быстро, так как он выполняет линейный поиск с использованием встроенного метода list.index() и оператора ==:

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

Ответ 6

Вот простой алгоритм, который использует методы списка:

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

Ответ 7

Если мы уточним проблему, говорящую о тестировании, если список содержит другой список с последовательностью, ответ может быть следующим однострочным:

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

Здесь модульные тесты, которые я использовал для настройки этого однострочного интерфейса:

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

Ответ 8

Я попытался сделать это максимально эффективным.

Он использует генератор; тем, кто не знаком с этими зверями, рекомендуется проверить их документацию и yield выражения.

В основном он создает генератор значений из подпоследовательности, которая может быть reset, отправив ему истинное значение. Если генератор reset, он начинает сдаваться снова с начала sub.

Затем он просто сравнивает последовательные значения sequence с выходами генератора, сбрасывая генератор, если они не совпадают.

Когда у генератора заканчиваются значения, т.е. достигает конца sub без reset, это означает, что мы нашли наше соответствие.

Так как он работает для любой последовательности, вы даже можете использовать его в строках, и в этом случае он ведет себя аналогично str.find, за исключением того, что он возвращает False вместо -1.

В качестве еще одного примечания: я считаю, что второе значение возвращаемого кортежа должно, в соответствии со стандартами Python, обычно быть выше. т.е. "string"[0:2] == "st". Но спецификация говорит иначе, так, как это работает.

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

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

Ответ 9

Я думаю, что это быстро...

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

Ответ 10

Самый маленький код:

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

Ответ 11

Вот мое решение. Эта функция поможет вам узнать, является ли B под-списком A. Сложность времени - это 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