Есть ли способ узнать, находится ли список элементов в большом списке без использования ключевого слова «in»?

Question

Я хочу сделать это. У меня есть два списка Python, один больше другого, и я хочу знать, есть ли способ проверить, находятся ли элементы меньшего списка в большом списке в том же порядке, например:

small_list = [4,2,5]
big_list = [1,2,5,7,2,4,2,5,67,8,5,13,45]

Я пытался использовать ключевое слово in , но оно не сработало: '(

Answer 1

def in_list(small, big):
    l_sml = len(small)
    l_big = len(big)
    return any((big[i:i+l_sml]==small for i in xrange(l_big-l_sml+1)))

print in_list([4,2,1], [1,2,3,4,2,1,0,5]) # True
print in_list([1,2,3], [1,2,4])           # False

Answer 2

Хм, может быть, это излишне, но вы можете использовать класс SequenceMatcher из difflib:

from difflib import SequenceMatcher 
small_list = [4,2,5]
big_list = [1,2,5,7,2,4,2,5,67,8,5,13,45]
print SequenceMatcher(None, small_list, big_list).get_matching_blocks()

документация difflib

Answer 3

Скорее не оптимизирован, просто демонстрирует общую стратегию:

tuple(small_list) in zip(big_list[:], big_list[1:], big_list[2:])

Прикольная молния делает это:

>>> zip(big_list[:], big_list[1:], big_list[2:])
[(1, 2, 5), (2, 5, 7), (5, 7, 2), (7, 2, 4), (2, 4, 2), (4, 2, 5), (2, 5, 67), (5, 67, 8), (67, 8, 5), (8, 5, 13), (5, 13, 45)]

Более оптимизированная версия:

from itertools import izip, islice
tuple(small_list) in izip(big_list, islice(big_list, 1, None), islice(big_list, 2, None))

Для обработки small_list длины любого размера:

from itertools import izip, islice
tuple(small_list) in izip(*(islice(big_list, i, None) for i in xrange(len(small_list))))

Answer 4

Это потому что small_list in big_list проверяет, равен ли элемент в big_list элементу small_list. Вместо этого вы хотите увидеть, совпадает ли фрагмент big_list с small_list.

def isSubList(slice, L):
    n = len(slice)
    for i in range(0, len(L) - n):
        if slice == L[i:i+n]:
            return True
    return False

isSubList(small_list, big_list)

Answer 5

Эта проблема сложнее, чем кажется. Если я не ошибаюсь, это особый случай самой длинной общей проблемы с подстрокой .

Для общего случая (произвольно большие списки) я бы использовал какой-то автомат конечного состояния , похожий на регулярное выражение. Я полагаю, что результат может быть рассчитан за O (mn).

Answer 6

Если вы знаете разумную границу своих чисел, вы можете преобразовать их в тип Python, чей оператор «in» делает это автоматически. Два, которых я знаю, это str и unicode.

Затем вы спрашиваете строки: чем меньше, тем больше, выполняется сравнение подстрок:

>>> small_list = [4,2,5]
>>> big_list = [1,2,5,7,2,4,2,5,67,8,5,13,45]
>>>
>>> def encode(lst):
      return u"".join(unichr(c) for c in lst)

>>> encode(small_list) in encode(big_list)
True

(Вы можете «кодировать» в str, если все числа в 0 <= x <= 255, вы можете «кодировать» в unicode, если все в 0 <= x <= sys.maxunicode).

Answer 7

Редактировать: оставив здесь ответ, но я не заметил требования, чтобы они были в одинаковом порядке. Это не соответствует этому требованию

Быстрый и грязный ответ. Исходя из ответа на Python - пересечение двух списков

small_list == filter( lambda x: x in big_list, small_list)

Answer 8

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

class mylist(list):
    def __contains__(self, lst):
        return ':'.join(map(str, lst)) in ':'.join(map(str, self))

small_list = mylist([4,2,5])
big_list = mylist([1,2,5,7,2,4,2,5,67,8,5,13,45])

print small_list in big_list

Редактировать: Адреса комментариев Джеффри.

Answer 9

вы можете использовать наборы

from sets import Set
small_set = set(small_list)
big_set = set(big_list)
small_set <= big_set

<= является оператором подмножества </p>

Answer 10

Там нет встроенного оператора, который делает это конкретное сравнение. Я предлагаю понимание списка или быстрый цикл.