поиск 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']]

Теперь у меня есть такой список:

['she', 'is', 'student']

Я хочу запросить большой список с этим и вернуть все списки, которые содержат слова в списке запросов в том же порядке. Могут быть пробелы, но порядок должен быть таким же. Как я могу это сделать? Я попытался использовать оператор in, но не получил желаемого результата.

Answer 1

Вы можете сравнить два списка с такой функцией, как эта.Как это работает, он просматривает ваш более короткий список и каждый раз, когда находит следующее слово в длинном списке, обрезает первую часть более длинного списка в этой точке.Если он не может найти слово, он возвращает ложь.

def is_sub_sequence(long_list, short_list):
    for word in short_list:
        if word in long_list:
            i = long_list.index(word)
            long_list = long_list[i+1:]
        else:
            return False
    return True

Теперь у вас есть функция, которая сообщает вам, является ли список нужным типом, вы можете отфильтровать все нужные вам списки из списка.списков », используя следующее понимание списка:

a = [['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']]


b = ['she', 'is', 'student']

filtered = [x for x in a if is_sub_sequence(x,b)]

Список filtered будет включать в себя только списки нужного типа.

Answer 2

Если все, что вас волнует, это то, что слова появляются в некотором порядке в массиве, вы можете использовать collections.deque и popleft для перебора списка, и если deque опустошен, вы нашли правильное совпадение:

from collections import deque

def find_gappy(arr, m):
  dq = deque(m)
  for word in arr:
    if word == dq[0]:
      dq.popleft()
      if not dq:
        return True
  return False

Сравнивая каждый word в arr с первым элементом dq, мы знаем, что когда мы находим совпадение, оно было найдено в правильном порядке, а затем мы popleft, поэтому мы теперь сравнивают со следующим элементом в deque.

Чтобы отфильтровать ваш начальный список, вы можете использовать простое понимание списка, которое фильтрует на основе результата find_gappy:

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

# [['she', 'is', 'a', 'student'], ['she', 'is', 'a', 'great', 'student'], ['she', 'is', 'a', 'very', 'very', 'exceptionally', 'good', 'student']]