Python: найдите список в составе членов другого списка (в порядке)
Если у меня есть это:
a='abcdefghij'
b='de'
Тогда это находит b в a:
b in a => True
Есть ли способ сделать подобную вещь со списками?
Вот так:
a=list('abcdefghij')
b=list('de')
b in a => False
Результат "False" понятен - потому что он правильно ищет элемент "de", а не (что мне нужно делать) d, за которым следует "e"
Это работы, я знаю:
a=['a', 'b', 'c', ['d', 'e'], 'f', 'g', 'h']
b=list('de')
b in a => True
Я могу хрустить данные, чтобы получить то, что хочу, - но есть ли короткий питонический способ сделать это?
Чтобы уточнить: мне нужно сохранить порядок здесь (b = ['e', 'd'], должен возвращать False).
И если это помогает, то у меня есть список списков: эти списки представляют все возможные пути (список посещенных узлов) от node -1 до node -x в ориентированном графе: я хочу "коэффициент" из общих путей на любых более длинных путях. (Ищите все неприводимые "атомные" пути, составляющие все более длинные пути).
Связанные
Ответы
Ответ 1
Не знаю, очень ли это питонично, но я бы сделал это следующим образом:
def is_sublist(a, b):
if a == []: return True
if b == []: return False
return b[:len(a)] == a or is_sublist(a, b[1:])
Более короткое решение предлагается в этом обсуждение, но оно испытывает те же проблемы, что и решения с set
- оно не учитывает порядок элементов.
UPDATE:
Вдохновленный MAK, я представил более сжатую и ясную версию моего кода.
UPDATE:
Есть проблемы с производительностью в отношении этого метода из-за копирования списка в срезах. Кроме того, поскольку он является рекурсивным, вы можете встретить предел рекурсии для длинных списков. Чтобы исключить копирование, вы можете использовать Numpy, которые создает представления, а не копии. Если вы столкнулись с проблемами производительности или рекурсии, вы должны использовать решение без рекурсии.
Ответ 2
Я подозреваю, что есть более питонические способы сделать это, но, по крайней мере, он выполняет свою работу:
l=list('abcdefgh')
pat=list('de')
print pat in l # Returns False
print any(l[i:i+len(pat)]==pat for i in xrange(len(l)-len(pat)+1))
Ответ 3
Я думаю, что это будет быстрее - он использует реализацию C list.index
для поиска первого элемента и идет оттуда.
def find_sublist(sub, bigger):
if not bigger:
return -1
if not sub:
return 0
first, rest = sub[0], sub[1:]
pos = 0
try:
while True:
pos = bigger.index(first, pos) + 1
if not rest or bigger[pos:pos+len(rest)] == rest:
return pos
except ValueError:
return -1
data = list('abcdfghdesdkflksdkeeddefaksda')
print find_sublist(list('def'), data)
Обратите внимание, что это возвращает позицию подсписок в списке, а не только True
или False
. Если вы хотите просто bool
, вы можете использовать это:
def is_sublist(sub, bigger):
return find_sublist(sub, bigger) >= 0
Ответ 4
Я приурочил принятое решение, мое раннее решение и новый с индексом. Лучше всего один с индексом.
EDIT: Я приурочил решение nosklo, это даже намного лучше, чем я придумал.:)
def is_sublist_index(a, b):
if not a:
return True
index = 0
for elem in b:
if elem == a[index]:
index += 1
if index == len(a):
return True
elif elem == a[0]:
index = 1
else:
index = 0
return False
def is_sublist(a, b):
return str(a)[1:-1] in str(b)[1:-1]
def is_sublist_copylist(a, b):
if a == []: return True
if b == []: return False
return b[:len(a)] == a or is_sublist_copylist(a, b[1:])
from timeit import Timer
print Timer('is_sublist([99999], range(100000))', setup='from __main__ import is_sublist').timeit(number=100)
print Timer('is_sublist_copylist([99999], range(100000))', setup='from __main__ import is_sublist_copylist').timeit(number=100)
print Timer('is_sublist_index([99999], range(100000))', setup='from __main__ import is_sublist_index').timeit(number=100)
print Timer('sublist_nosklo([99999], range(100000))', setup='from __main__ import sublist_nosklo').timeit(number=100)
Выход в секундах:
+4,51677298546
4.5824368
+1,87861895561
+0,357429027557
Ответ 5
Итак, если вас не беспокоит порядок, который появляется подмножеством, вы можете сделать:
a=list('abcdefghij')
b=list('de')
set(b).issubset(set(a))
True
Отредактируйте после того, как вы уточните: если вам нужно сохранить порядок, и список действительно символов, как в вашем вопросе, вы можете использовать:
''.join(a).find(''.join(b)) > 0
Ответ 6
Это должно работать с любыми парами списков, сохраняя порядок.
Проверяет, является ли b вспомогательным списком
def is_sublist(b,a):
if len(b) > len(a):
return False
if a == b:
return True
i = 0
while i <= len(a) - len(b):
if a[i] == b[0]:
flag = True
j = 1
while i+j < len(a) and j < len(b):
if a[i+j] != b[j]:
flag = False
j += 1
if flag:
return True
i += 1
return False
Ответ 7
Не уверен, насколько сложным является ваше приложение, но для сопоставления шаблонов в списках pyparsing очень умный и простой в использовании.
Ответ 8
>>>''.join(b) in ''.join(a)
True
Ответ 9
Используйте строковое представление списков и удалите квадратные скобки.:)
def is_sublist(a, b):
return str(a)[1:-1] in str(b)
EDIT: Правильно, есть ложные срабатывания... например. is_sublist([1], [11])
. Дрянной ответ.:)