Как найти последовательность в списке a, состоящую из k значений в любом порядке из второго списка b?

Рейтинг: 1Ответов: 1Опубликовано: 22.09.2014

Как найти в первом списке (a = [ 12, 43, 65, 101, 234, 26, 558, 534, 301, 65, 65... и т.д.] .... до 700 значений) последовательность 8 значений в любом порядке из второго списка (b = [ 48, 73, 101, 558, 43, 303... и т.д.] ... до 20 значений)?

Нужно найти только последовательность, разбросанные поштучные совпадения из 1-3 значений не интересуют.

python
Источник: Stack Overflow на русском

Ответы

▲ 3

Чтобы найти 8 значений из набора b, которые идут подряд в списке a:

k = 8
bset = frozenset(b)
for i in range(len(a) - k + 1):
    if bset.issuperset(a[i:i+k]):
       print("Found {seq} at {i}".format(seq=a[i:i+k], i=i))
       break
else:
    print("Not found")

Дупликаты разрешены, например, если одно значение из b повторяется 8 раз подряд в a, то считается что последовательность найдена.

Сложность алгоритма O(n*k). Учитывая, что n и k маленькие, не имеет смысла усложнять код ради скорости.