Как удалить все вхождения списка из списка

Ответ 1

Вам придется реализовать его самостоятельно. Вот основная идея:

def remove_sublist(lst, sub):
    i = 0
    out = []
    while i < len(lst):
        if lst[i:i+len(sub)] == sub:
            i += len(sub)
        else:
            out.append(lst[i])
            i += 1
    return out

Это выполняется по каждому элементу исходного списка и добавляет его в выходной список, если он не является членом подмножества. Эта версия не очень эффективна, но она работает как пример строки, который вы предоставили, в том смысле, что он создает новый список, не содержащий ваш поднабор. Он также работает для произвольных типов элементов, если они поддерживают ==. Удаление [1,1,1] из [1,1,1,1] корректно приведет к [1], как к строке.

Вот ссылка IDEOne, показывающая результат

>>> remove_sublist([1, 'a', int, 3, float, 'a', int, 5], ['a', int])
[1, 3, <class 'float'>, 5]

Ответ 2

Попробуйте del и slicing. Худшей сложностью является O(N^2).

sub_list=['a', int]
big_list=[1, 'a', int, 3, float, 'a', int, 5]
i=0
while i < len(big_list):
    if big_list[i:i+len(sub_list)]==sub_list:
        del big_list[i:i+len(sub_list)]
    else:
        i+=1

print(big_list)

результат:

[1, 3, <class 'float'>, 5]

Ответ 3

Рекурсивный подход:

def remove(lst, sub):
    if not lst:
        return []
    if lst[:len(sub)] == sub:
        return remove(lst[len(sub):], sub)
    return lst[:1] + remove(lst[1:], sub)
print(remove(big_list, sub_list))

Эти результаты:

[2, 3, 4]

Ответ 4

Улучшенная версия для проверки lst[i:i+len(sub)] < len(lst)

def remove_sublist(lst, sub):
    i = 0
    out = []
    sub_len = len(sub)
    lst_len = len(lst)
    while i < lst_len:
        if (i+sub_len) < lst_len:
            if lst[i: i+sub_len] == sub:
                i += sub_len
            else:
                out.append(lst[i])
                i += 1
        else:
            out.append(lst[i])
            i += 1

    return out

Ответ 5

Как насчет этого:

def remove_sublist(lst, sub):
    max_ind_sub = len(sub) - 1
    out = []
    i = 0
    tmp = []

    for x in lst:
        if x == sub[i]:
            tmp.append(x)
            if i < max_ind_sub: # partial match 
                i += 1
            else:  # found complete match
                i = 0
                tmp = []
        else:
            if tmp:  # failed partial match 
                i = 0
                out += tmp
            if x == sub[0]:  # partial match
                i += 1
                tmp = [x]
            else:
                out.append(x)

    return out

Представление:

lst = [2, 1, 2, 3, 1, 2, 4]
sub = [1, 2]
%timeit remove_sublist(lst, sub)  # solution of Mad Physicist
%timeit remove_sublist_new(lst, sub)
>>> 2.63 µs ± 112 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> 1.77 µs ± 13.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Обновить

У моего первого решения была ошибка. Был в состоянии исправить это (обновил мой код выше), но теперь метод выглядит более сложным. С точки зрения производительности он по-прежнему работает лучше, чем решение Mad Physicist на моей локальной машине.

Ответ 6

Используйте itertools.zip_longest для создания n наборов элементов (где n - длина sub_list), а затем отфильтруйте текущий элемент и следующие n-1 элементы, когда один из элементов соответствует под-списку

>>> from itertools import zip_longest, islice
>>> itr = zip_longest(*(big_list[i:] for i in range(len(sub_list))))
>>> [sl[0] for sl in itr if not (sl == tuple(sub_list) and next(islice(itr, len(sub_list)-2, len(sub_list)-1)))]
[2, 3, 4]

Чтобы повысить эффективность, вы можете рассчитать tuple(sub_list) и len(sub_list) прежде чем вы начнете фильтровать

>>> l = len(sub_list)-1
>>> tup = tuple(sub_list)
>>> [sl[0] for sl in itr if not (sl == tup and next(islice(itr, l-1, l)))]
[2, 3, 4]

Ответ 7

Обновление: библиотека more_itertools выпустила more_itertool.replace, инструмент, который решает эту проблему (см. Вариант 3).

Во-первых, вот некоторые другие варианты, которые работают с универсальными итерами (списки, строки, итераторы и т.д.):

Код

Вариант 1 - без библиотек:

def remove(iterable, subsequence):
    """Yield non-subsequence items; sans libraries."""
    seq = tuple(iterable)
    subsequence = tuple(subsequence)
    n = len(subsequence)
    skip = 0

    for i, x in enumerate(seq):
        slice_ = seq[i:i+n]
        if not skip and (slice_ == subsequence):
            skip = n
        if skip:
            skip -= 1
            continue
        yield x   

Вариант 2 - с more_itertools

import more_itertools as mit


def remove(iterable, subsequence):
    """Yield non-subsequence items."""
    iterable = tuple(iterable)
    subsequence = tuple(subsequence)
    n = len(subsequence)
    indices = set(mit.locate(mit.windowed(iterable, n), pred=lambda x: x == subsequence))

    it_ = enumerate(iterable)
    for i, x in it_:
        if i in indices:
            mit.consume(it_, n-1)
        else:
            yield x

демонстрация

list(remove(big_list, sub_list))
# [2, 3, 4]

list(remove([1, 2, 1, 2], sub_list))
# []

list(remove([1, "a", int, 3, float, "a", int, 5], ["a", int]))
# [1, 3, float, 5]

list(remove("11111", "111"))
# ['1', '1']

list(remove(iter("11111"), iter("111")))
# ['1', '1']

Вариант 3 - с more_itertools.replace:

демонстрация

pred = lambda *args: args == tuple(sub_list)
list(mit.replace(big_list, pred=pred, substitutes=[], window_size=2))
# [2, 3, 4]

pred=lambda *args: args == tuple(sub_list)
list(mit.replace([1, 2, 1, 2], pred=pred, substitutes=[], window_size=2))
# []

pred=lambda *args: args == tuple(["a", int])
list(mit.replace([1, "a", int, 3, float, "a", int, 5], pred=pred, substitutes=[], window_size=2))
# [1, 3, float, 5]

pred=lambda *args: args == tuple("111")
list(mit.replace("11111", pred=pred, substitutes=[], window_size=3))
# ['1', '1']

pred=lambda *args: args == tuple(iter("111"))
list(mit.replace(iter("11111"), pred=pred, substitutes=[], window_size=3))
# ['1', '1']

Детали

Во всех этих примерах мы просматриваем основную последовательность с меньшими фрагментами окна. Мы даем то, что не найдено в срезе, и пропускаем все, что находится на срезе.

Вариант 1 - без библиотек

Итерируйте перечислимую последовательность и оцените срезы размера n (длина подпоследовательности). Если предстоящий срез равен подпоследовательности, сбросьте skip и дайте элемент. В противном случае пройдите мимо него. skip дорожки, сколько раз, чтобы продвинуть цикл, например, sublist имеет размер n=2, поэтому он пропускает два раза за матч.

Обратите внимание: вы можете преобразовать этот параметр, чтобы работать с последовательностями, удалив первые два назначения кортежей и заменив iterable параметр seq, например def remove(seq, subsequence): iterable def remove(seq, subsequence):

Вариант 2 - с more_itertools

Индексы расположены для каждой соответствующей подпоследовательности в итерируемой. При повторении итератора с перечислением, если индекс найден в indices, оставшаяся подпоследовательность пропускается путем потребления следующих элементов n-1 из итератора. В противном случае появляется элемент.

Установите эту библиотеку через > pip install more_itertools.

Вариант 3 - с more_itertools.replace:

Этот инструмент заменяет подпоследовательность элементов, определенных в предикате, с заменяющими значениями. Чтобы удалить элементы, мы заменяем пустой контейнер, например substitutes=[]. Длина замененных элементов указана параметром window_size (это значение равно длине подпоследовательности).

Ответ 8

Более читаемый, чем любой выше и без дополнительной памяти:

def remove_sublist(sublist, mainlist):

    cursor = 0

    for b in mainlist:
        if cursor == len(sublist):
            cursor = 0
        if b == sublist[cursor]:
            cursor += 1
        else:
            cursor = 0
            yield b

    for i in range(0, cursor):
        yield sublist[i]

Это для onliner, если вы хотите функцию из библиотеки, пусть это будет

[x for x in remove_sublist([1, 2], [2, 1, 2, 3, 1, 2, 4])]

Ответ 9

Разный подход в Python 2.x!

from more_itertools import locate, windowed
big_list = [1, 2, 1, 2, 1]
sub_list = [1, 2, 1]

"""
Fetching all starting point of indexes (of sub_list in big_list)
to be removed from big_list. 
"""

i = list(locate(windowed(big_list, len(sub_list)), pred=lambda x: x==tuple(sub_list)))

""" 
Here i comes out to be [0, 2] in above case. But index from 2 which 
includes 1, 2, 1 has last 1 from the 1st half of 1, 2, 1 so further code is
to handle this case.
PS: this won't come for-
big_list = [2, 1, 2, 3, 1, 2, 4]
sub_list = [1, 2]
as here i comes out to be [1, 4]
"""

# The further code.
to_pop = []
for ele in i:
    if to_pop:
        if ele == to_pop[-1]:
            continue
    to_pop.extend(range(ele, ele+len(sub_list)))

# Voila! to_pop consists of all the indexes to be removed from big_list.

# Wiping out the elements!
for index in sorted(to_pop, reverse=True):
    del big_list[index]

Обратите внимание, что вам нужно удалить их в обратном порядке, чтобы не отбрасывать последующие индексы.

В Python3 подпись locate() будет отличаться.

Ответ 10

(Для окончательного подхода см. Последний фрагмент кода)

Я бы подумал, что простого преобразования строк будет достаточно:

big_list = [2, 1, 2, 3, 1, 2, 4]
sub_list = [1, 2]

new_list = list(map(int, list((''.join(map(str, big_list))).replace((''.join(map(str, sub_list))), ''))))

Я по сути делаю поиск/замену строковыми эквивалентами списков. Затем я привязываю их к целым числам, чтобы сохранить исходные типы переменных. Это будет работать для любого размера большого и вспомогательного списков.

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

Для этого я составил решение с другим подходом:

new_list = []
i = 0
while new_list != big_list:
    if big_list[i:i+len(sub_list)] == sub_list:
        del big_list[i:i+len(sub_list)]
    else:
        new_list.append(big_list[i])
        i += 1

По сути, я удаляю каждый дубликат sub_list, когда я их нахожу, и добавляю к new_list, когда я нахожу элемент, который не является частью дубликата. Когда new_list и big_list равны, все дубликаты были найдены, и я останавливаюсь. Я не использовал попытку - кроме как я не думаю, что должны быть какие-либо ошибки индексирования.

Это похоже на ответ @MadPhysicist и имеет примерно такую же эффективность, но моя потребляет меньше памяти.

Этот второй подход будет работать для любого типа объектов с любым размером списков и, следовательно, гораздо более гибким, чем первый подход. Однако первый подход выполняется быстрее, если ваши списки являются целыми числами.

Однако я еще не закончил! Я придумал однострочный список, который имеет те же функциональные возможности, что и второй подход!

import itertools
new_list = [big_list[j] for j in range(len(big_list)) if j not in list(itertools.chain.from_iterable([ list(range(i, i+len(sub_list))) for i in [i for i, x in enumerate(big_list) if x == sub_list[0]] if big_list[i:i+len(sub_list)] == sub_list ]))]

Первоначально это кажется сложным, но я заверяю вас, что это довольно просто! Во-первых, я создаю список индексов, в которых произошел первый элемент подсписок. Затем, для каждого из этих индексов, я проверяю, образуют ли следующие подстроки следующие элементы. Если они это сделают, диапазон индексов, которые образуют дубликат подписок, добавляется в другой список. Впоследствии я использую функцию itertools, чтобы сгладить результирующий список списков. Каждый элемент в этом сплюснутом списке является индексом, который находится в дубликате подписок. Наконец, я создаю новый_list, который состоит из каждого элемента big_list, который имеет индекс, не найденный в сплющенном списке.

Я не думаю, что этот метод находится в любом другом ответе. Мне это нравится больше всего, так как он довольно аккуратный, когда вы понимаете, как он работает и очень эффективен (из-за характера понимания списков).

Ответ 11

Вы можете использовать рекурсию с генератором:

def remove(d, sub_list):
   if d[:len(sub_list)] == sub_list and len(sub_list) <= len(d[:len(sub_list)]):
      yield from [[], remove(d[len(sub_list):], sub_list)][bool(d[len(sub_list):])]
   else:
      yield d[0]
      yield from [[], remove(d[1:], sub_list)][bool(d[1:])]

tests = [[[2, 1, 2, 3, 1, 2, 4], [1, 2]], [[1, 2, 1, 2], [1, 2]], [[1, 'a', int, 3, float, 'a', int, 5], ['a', int]], [[1, 1, 1, 1, 1], [1,1,1]]]
for a, b in tests:
  print(list(remove(a, b)))

Вывод:

[2, 3, 4]
[]
[1, 3, <class 'float'>, 5]
[1, 1]

Ответ 12

Просто для удовольствия, вот ближайшая аппроксимация однострочного:

from functools import reduce

big_list = [2, 1, 2, 3, 1, 2, 4]
sub_list = [1, 2]
result = reduce(lambda r, x: r[:1]+([1]+r[2:-r[1]],[min(len(r[0]),r[1]+1)]+r[2:])[r[-r[1]:]!=r[0]]+[x], big_list+[0], [sub_list, 1])[2:-1]

Не верьте, что он работает? Проверьте это на IDEone !

Конечно, это далеко не эффективно и отвратительно загадочно, однако это должно помочь убедить OP принять ответ @Mad Physicist.

Ответ 13

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

В одной строке вы можете сделать это так

map(int,list(("".join(map(str, big_list))).replace("".join(map(str, sub_list)),'').replace(''.join((map(str, sub_list))[::-1]),'')))

вход

big_list = [1, 2, 1, 2, 1]
sub_list = [1, 2, 1]

Вывод

[2, 1]

вход

big_list = [2, 1, 2, 3, 1, 2, 4]
sub_list = [1, 2]

Ouput

[2, 3, 4]

Ответ 14

Как можно компактнее:

a=[]
for i in range(0,len(big_list)):
    if big_list[i]==1 and big_list[i+1]==2:
        a.extend((i,i+1))
[big_list[x] for x in [x for x in range(len(big_list)) if x not in a]]

Out[101]: [2, 3, 4]

Тот же подход в R:

big_list <- c(2, 1, 2, 3, 1, 2, 4)
sub_list <- c(1,2)

a<-c()
for(i in 1:(length(big_list)-1)){if (all(big_list[c(i,i+1)]==sub_list)) a<-c(a,c(i,i+1)) }
big_list[-a]
[1] 2 3 4

Я думаю, что R проще.

[big_list[x] for x in [x for x in range(len(big_list)) if x not in a]] эквивалентно big_list[-a]