Проверьте на присутствие нарезанного списка в Python
Я хочу записать функцию, которая определяет, существует ли подсписок в большем списке.
list1 = [1,0,1,1,1,0,0]
list2 = [1,0,1,0,1,0,1]
#Should return true
sublistExists(list1, [1,1,1])
#Should return false
sublistExists(list2, [1,1,1])
Существует ли функция Python, которая может сделать это?
5 ответов
Если вы уверены, что ваши входные данные будут содержать только одиночные цифры 0 и 1, тогда вы можете преобразовать их в строки:
def sublistExists(list1, list2):
return ''.join(map(str, list2)) in ''.join(map(str, list1))
Это создает две строки, поэтому это не самое эффективное решение, но поскольку оно использует оптимизированный алгоритм поиска строки в Python этого, вероятно, достаточно для большинства целей.
Если эффективность очень важна, вы можете взглянуть на алгоритм поиска строк Бойера-Мура , адаптированный для работы со списками.
Наивный поиск имеет наихудший случай O (n * m), но может быть подходящим, если вы не можете использовать трюк с преобразованием в строку и вам не нужно беспокоиться о производительности.
Давайте немного поработаем, ладно? :)
def contains_sublist(lst, sublst):
n = len(sublst)
return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1))
Обратите внимание, что any () остановится при первом совпадении sublst в пределах lst - или завершится ошибкой, если совпадения нет, после O (m * n) ops
Если я правильно понимаю, у вас есть больший список, например:
list_A= ['john', 'jeff', 'dave', 'shane', 'tim']
, затем есть другие списки
list_B= ['sean', 'bill', 'james']
list_C= ['cole', 'wayne', 'jake', 'moose']
, а затем я добавляю списки B и C к списку A
list_A.append(list_B)
list_A.append(list_C)
поэтому, когда я печатаю list_A
print (list_A)
, я получаю следующий результат
['john', 'jeff', 'dave', 'shane', 'tim', ['sean', 'bill', 'james'], ['cole', 'wayne', 'jake', 'moose']]
, теперь я хочу проверить, существует ли подсписок:
for value in list_A:
value= type(value)
value= str(value).strip('<>').split()[1]
if (value == "'list'"):
print "True"
else:
print "False"
это даст вам «Истина», если у вас есть подсписок внутри большего списка.
Вот способ, который будет работать для простых списков и который немного менее хрупок, чем способ Марка
def sublistExists(haystack, needle):
def munge(s):
return ", "+format(str(s)[1:-1])+","
return munge(needle) in munge(haystack)
Нет функции, о которой я знаю
def sublistExists(list, sublist):
for i in range(len(list)-len(sublist)+1):
if sublist == list[i:i+len(sublist)]:
return True #return position (i) if you wish
return False #or -1
Как отметил Марк, это не самый эффективный поиск (это O(n*m)). К этой проблеме можно подойти примерно так же, как к поиску строк.