Python: найдите список в членах другого списка (в порядке)
Если у меня есть это:
a='abcdefghij'
b='de'
Затем это находит b в a:
b in a => True
Существует ли способ сделать подобную вещь со списками? Как это:
a=list('abcdefghij')
b=list('de')
b in a => False
'Ложный' результат понятен - потому что его справедливо поиск элемента 'de', а не (что я, оказывается, хочу, чтобы он сделал), 'd' сопровождаемый 'e'
Это - работы, я знаю:
a=['a', 'b', 'c', ['d', 'e'], 'f', 'g', 'h']
b=list('de')
b in a => True
Я могу уплотнить данные для получения то, что я хочу - но есть ли короткий Pythonic способ сделать это?
Разъясниться: Я должен сохранить упорядочивание здесь (b = ['e', 'd'], должен возвратить False).
И если помогает, что я имею, список списков: эти списки представляют все возможные пути (список посещаемых узлов) от узла 1 к узлу-x в ориентированном графе: Я хочу 'включить' общие пути в любые более длинные пути. (Настолько ищущий все неприводимые 'атомарные' пути, который составляющая все более длинные пути).
Похожие страницы
8 ответов
Не знаю, насколько это питонично, но я бы сделал это следующим образом:
def is_sublist(a, b):
if not a: return True
if not b: return False
return b[:len(a)] == a or is_sublist(a, b[1:])
Более короткое решение предлагается в этом обсуждении , но он страдает теми же проблемами, что и решения с набором - он не учитывает порядок элементов.
ОБНОВЛЕНИЕ:
Вдохновленный MAK, я представил более сжатую и понятную версию своего кода.
ОБНОВЛЕНИЕ: У этого метода есть проблемы с производительностью из-за копирования списка в срезах. Кроме того, поскольку он рекурсивен, вы можете столкнуться с ограничением рекурсии для длинных списков. Чтобы исключить копирование, вы можете использовать Numpy срезы, которые создают представления, а не копии . Если вы столкнулись с проблемами производительности или ограничения рекурсии, вам следует использовать решение без рекурсии.
Я подозреваю, что есть и другие питонические способы сделать это, но, по крайней мере, он выполняет свою работу:
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))
Я думаю, это будет быстрее - Он использует реализацию 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
Я синхронизировал принятое решение, мое предыдущее решение и новое с индексом. Тот, у кого есть индекс, явно лучший.
РЕДАКТИРОВАТЬ: Я рассчитал решение носкло, оно даже намного лучше, чем то, что я придумал. :)
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
Итак, если вас не беспокоит порядок появления подмножества, вы можете сделать:
a=list('abcdefghij')
b=list('de')
set(b).issubset(set(a))
True
Отредактировать после уточнения: Если вам нужно сохранить порядок, и список действительно состоит из символов, как в вашем вопросе, вы можете использовать:
''.join(a).find(''.join(b)) > 0
Используйте строковое представление списков и удалите квадратные скобки. :)
def is_sublist(a, b):
return str(a)[1:-1] in str(b)
РЕДАКТИРОВАТЬ: Да, есть ложные срабатывания ... например. is_sublist ([1], [11]) . Дерьмовый ответ. :)
Не уверен, насколько сложно ваше приложение, но для сопоставления шаблонов в списках pyparsing очень умный и простой в использовании.