Тестирование, если список содержит другой список с 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

Проблема большинства ответов в том, что они хороши для уникальных предметов в списке. Если элементы не являются уникальными, и вы все еще хотите знать, есть ли пересечение, вы должны считать элементы:

from collections import Counter as count

def listContains(l1, l2):
  list1 = count(l1)
  list2 = count(l2)

  return list1&list2 == list1

print( listContains([1,1,2,5], [1,2,3,5,1,2,1]) ) # Returns True
print( listContains([1,1,2,8], [1,2,3,5,1,2,1]) ) # Returns False

Вы также можете вернуть пересечение, используя ''.join(list1&list2)

Answer 2

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

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

Answer 3

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

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

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

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

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

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