Как проверить, содержит ли список другой список (т.е. подпоследовательность). Скажем, была функция, которая содержит:
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]
Edit:
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]
Вот моя версия:
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.
Если все элементы уникальны, вы можете использовать наборы.
>>> items = set([-1, 0, 1, 2])
>>> set([1, 2]).issubset(items)
True
>>> set([1, 3]).issubset(items)
False
После редактирования 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
Могу ли я смиренно предложить алгоритм Рабина-Карпа, если список big действительно большой. Ссылка даже содержит почти полезный код в почти-Python.
Это работает и довольно быстро, так как он выполняет линейный поиск с использованием встроенного метода 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
Вот простой алгоритм, который использует методы списка:
#!/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()
Если мы уточним проблему, говорящую о тестировании, если список содержит другой список с последовательностью, ответ может быть следующим однострочным:
def contains(subseq, inseq):
return any(inseq[pos:pos + len(subseq)] == subseq for pos in range(0, len(inseq) - len(subseq) + 1))
Здесь модульные тесты, которые я использовал для настройки этого однострочного интерфейса:
Я попытался сделать это максимально эффективным.
Он использует генератор; тем, кто не знаком с этими зверями, рекомендуется проверить их документацию и 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
Я думаю, что это быстро...
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
Самый маленький код:
def contains(a,b):
str(a)[1:-1].find(str(b)[1:-1])>=0
Вот мое решение. Эта функция поможет вам узнать, является ли 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