поиск gappy sublists в определенном диапазоне

Question

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

 [['she', 'is', 'a', 'student'],
 ['she', 'is', 'a', 'lawer'],
 ['she', 'is', 'a', 'great', 'student'],
 ['i', 'am', 'a', 'teacher'],
 ['she', 'is', 'a', 'very', 'very', 'exceptionally', 'good', 'student']] 

, и я хочу запросить его, используя matches = ['she', 'is', 'student'], с намерением вывести из запрошенного списка все подсписки, содержащие элементы matches в одном и том жепорядок.Единственное отличие от вопроса в ссылке заключается в том, что я хочу добавить параметр range в функцию find_gappy, чтобы он не получал списки, в которых разрыв между элементами превышает указанный диапазон.Например, в приведенном выше примере я хотел бы функцию, подобную этой:

matches = ['she', 'is', 'student']
x = [i for i in x if find_gappy(i, matches, range=2)]

, которая будет возвращать:

[['she', 'is', 'a', 'student'], ['she', 'is', 'a', 'great', 'student']]

Последний элемент не появляется, так как в предложенииshe is a very very exceptionally good student, расстояние между a и good превышает предел диапазона.

Как я могу написать такую ​​функцию? Разрыв между

Answer 1

Вот один из способов, который также учитывает порядок элементов в списке match:

In [102]: def find_gappy(all_sets, matches, gap_range=2):
     ...:     zip_m = list(zip(matches, matches[1:]))
     ...:     for lst in all_sets:
     ...:         indices = {j: i for i, j in enumerate(lst)}
     ...:         try:
     ...:             if all(0 <= indices[j]-indices[i] - 1 <= gap_range for i, j in zip_m):
     ...:                 yield lst
     ...:         except KeyError:
     ...:             pass
     ...:         
     ...:   

Демонстрация:

In [110]: lst = [['she', 'is', 'a', 'student'],
     ...:  ['student', 'she', 'is', 'a', 'lawer'],  # for order check
     ...:  ['she', 'is', 'a', 'great', 'student'],
     ...:  ['i', 'am', 'a', 'teacher'],
     ...:  ['she', 'is', 'a', 'very', 'very', 'exceptionally', 'good', 'student']] 
     ...:  

In [111]: 

In [111]: list(find_gappy(lst, ['she', 'is', 'student'], gap_range=2))
Out[111]: [['she', 'is', 'a', 'student'], ['she', 'is', 'a', 'great', 'student']]

Если в вашем файле есть повторяющиеся словаВ подсписках вы можете использовать defaultdict() для отслеживания всех индексов и использовать itertools.prodcut для сравнения разрыва для всех упорядоченных произведений пар слов.

In [9]: from collections import defaultdict
In [10]: from itertools import product

In [10]: def find_gappy(all_sets, matches, gap_range=2):
    ...:     zip_m = list(zip(matches, matches[1:]))
    ...:     for lst in all_sets:
    ...:         indices = defaultdict(list)
    ...:         for i, j in enumerate(lst):
    ...:             indices[j].append(i)
    ...:         try:
    ...:             if all(any(0 <= v - k - 1 <= gap_range for k, v in product(indices[j], indices[i])) for i, j in zip_m):
    ...:                 yield lst
    ...:         except KeyError:
    ...:             pass

Answer 2

Техника в связанном вопросе достаточно приличная, вам просто нужно добавить подсчет пробелов по пути и, поскольку вам не нужен глобальный подсчет, сбрасывать счетчик всякий раз, когда вы встречаете совпадение.Что-то вроде:

import collections

def find_gappy(source, matches, max_gap=-1):
    matches = collections.deque(matches)
    counter = max_gap  # initialize as -1 if you want to begin counting AFTER the first match
    for word in source:
        if word == matches[0]:
            counter = max_gap  # or remove this for global gap counting
            matches.popleft()
            if not matches:
                return True
        else:
            counter -= 1
            if counter == -1:
                return False
    return False

data = [['she', 'is', 'a', 'student'],
        ['she', 'is', 'a', 'lawer'],
        ['she', 'is', 'a', 'great', 'student'],
        ['i', 'am', 'a', 'teacher'],
        ['she', 'is', 'a', 'very', 'very', 'exceptionally', 'good', 'student']]

matches = ['she', 'is', 'student']
x = [i for i in data if find_gappy(i, matches, 2)]
# [['she', 'is', 'a', 'student'], ['she', 'is', 'a', 'great', 'student']]

В качестве бонуса вы можете использовать его в качестве исходной функции, подсчет пробелов применяется только в том случае, если вы передаете положительное число как max_gap.