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

Question

Как я могу проверить, содержит ли список другой список (т. Е. Это смежная подпоследовательность).Допустим, была вызвана функция содержит:

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]

Редактировать:

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

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

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

Answer 2

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

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

Возвращает кортеж (начало, конец + 1), так как я думаю, что это более питонично, как отмечает Эндрю Джаффе в своем комментарии. Он не разбивает никакие подсписки, поэтому должен быть достаточно эффективным.

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

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

Answer 3

Для этого есть функция all() и any().Чтобы проверить, содержит ли list1 ВСЕ элементы в списке list2

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

Чтобы проверить, содержит ли list1 ЛЮБЫЕ элементы в списке list2

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

, переменная будет иметь логическое значение (TRUE / FALSE).

Answer 4

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

Answer 5

После редактирования ОП:

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 6

Это работает и довольно быстро, поскольку выполняет линейный поиск с использованием встроенного метода 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

Answer 7

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

Answer 8

Наименьший код:

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

Answer 9

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

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

Answer 10

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

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