Видя, существует ли список в другом списке?

Question

В основном, скажем, у меня есть:

>>> a = [1,3,2,2,2]
>>> b = [1,3,2]

Я хочу посмотреть, существуют ли все элементы в b внутри a и в том же порядке. Таким образом, для приведенного выше примера b будет существовать в пределах.

Я надеюсь, что это действительно простой однострочный ответ.

Answer 1

Это простой алгоритм O (n * m):

any(a[i:i + len(b)] == b for i in range(len(a) - len(b) + 1))

Обратите внимание, что это не самый быстрый способ сделать это. Если вам нужна высокая производительность, вы можете использовать методы, аналогичные используемым в алгоритмах поиска строк .

Answer 2

Если под «в том же порядке» вы имели в виду подпоследовательность (в отличие от подстроки), то этот не однострочный должен работать быстро:

  def is_subsequence(x, y):
    i, j = 0, 0
    while i < len(x) and j < len(y):
      if x[i] == y[j]:
        i += 1
      j += 1
    return i == len(x)

Answer 3

Вот решение, которое работает для списков целых.

Включите, например, [1, 3, 2] в строку «1», «3», «2». Затем используйте встроенное включение строк, чтобы увидеть, находится ли оно в другом списке.

repr(map(str, b))[1:-1] in repr(map(str, a))[1:-1]

Answer 4

Извините, но то, что вы хотите сделать, по сути то же самое, что сопоставление строк (хотя со списками вместо строк). Возможно, вы захотите взглянуть на Кнут-Моррис-Пратт или Бойера-Мура для линейного алгоритма времени.

РЕДАКТИРОВАТЬ:
Я предполагаю, что под «по порядку» вы подразумеваете последовательно любое место в последовательности. Если они могут быть разделены другими элементами между ними, то это не то решение, которое вам нужно.

Answer 5

если "в том же порядке",

>>> a = [1,3,2,2,2]
>>> b = [1,3,2]
>>> ' '.join(map(str,b)) in ' '.join(map(str,a))
True

>>> a = [1,1,2,2,2,13,2]
>>> b = [1,3,2]
>>> ' '.join(map(str,b)) in ' '.join(map(str,a))
False

Answer 6

Это, вероятно, не очень эффективно, но вы можете использовать:

In [1]: a = [1,3,2,2,2]

In [2]: b = [1,3,2]

In [3]: b == [val for val in a if val in b]
Out[3]: False

In [4]: a = [6,1,3,2,5,4]

In [5]: b == [val for val in a if val in b]
Out[5]: True

Первый тест возвращает False из-за дубликатов 2. Вопрос в том, как вы хотите иметь дело с дубликатами в целом. Если вы хотите вырезать их только в конце, вы можете обрезать список до длины a:

In [6]: a = [1,3,2,2,2]

In [7]: b == [val for val in a if val in b][:len(b)]
Out[7]: True