如何从列表中删除所有子列表的出现

Question

我有两个列表：

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

我想从big_list中删除所有sub_list出现的情况。

结果应该是[2, 3, 4]

对于字符串，您可以使用以下内容：

'2123124'.replace('12', '')

据我所知，这种方法无法用于列表。

这不是从列表中删除子列表的重复问题，因为我想从大列表中删除所有子列表。在另一个问题中，结果应该是[5,6,7,1,2,3,4]。

更新：为简单起见，在此示例中采用整数。但列表项可以是任意对象。

更新2：

如果big_list = [1, 2, 1, 2, 1]且sub_list = [1, 2, 1]，

我想要的结果是[2, 1]（类似于'12121'.replace（'121'，''））

更新3：

我不喜欢将源代码从StackOverflow粘贴到我的代码中。这就是为什么我在software-recommendations上创建了第二个问题的原因： https://softwarerecs.stackexchange.com/questions/51273/library-to-remove-every-occurrence-of-sub-list-from-list-python 更新4：如果您知道一种可以通过一种方法调用来解决此问题的库，请将其编写为答案，因为这是我首选的解决方案。

测试应通过此测试：

def test_remove_sub_list(self):
    self.assertEqual([1, 2, 3], remove_sub_list([1, 2, 3], []))
    self.assertEqual([1, 2, 3], remove_sub_list([1, 2, 3], [4]))
    self.assertEqual([1, 3], remove_sub_list([1, 2, 3], [2]))
    self.assertEqual([1, 2], remove_sub_list([1, 1, 2, 2], [1, 2]))
    self.assertEquals([2, 1], remove_sub_list([1, 2, 1, 2, 1], [1, 2, 1]))
    self.assertEqual([], remove_sub_list([1, 2, 1, 2, 1, 2], [1, 2]))

- guettli

---

可能是从列表中删除子列表的重复问题。 - glibdud

@Marcus.Aurelianus 可能是因为那个答案上的大多数赞发生在几天内：Stack Overflow 每天的声望上限为200。因此，如果超过20人在24小时内给您的答案点赞，则只计算前20个点赞（×10 = 200分）。 - Konrad Rudolph

@guettli. 为什么不将函数放到你的库中，然后将其用作一行代码呢？ - Mad Physicist

考虑到你之前说过的话，最后那句话“我喜欢重复使用软件”的说法充其量是虚伪的。除了你所加的完全人为的限制以外，没有任何阻止你重新使用软件的因素。 - Mad Physicist

如果有一个外部库可以解决这个问题，你是需要一个用C语言编写的优化解决方案，还是接受用Python实现的东西？在后一种情况下，我可以将我的解决方案上传到GitHub，并附带一个setup.py文件来调用它。 - Mad Physicist

Answer 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]

- Mad Physicist

---

加油，你可以做得比这更好！=) - lenik

@lenik。很好。希望这样不会太懒。不幸的是，我无法想出更简化的解决方案。而且在原地完成也不会更美观。 - Mad Physicist

@jpp。我认为这些问题并不相等。有些事情你可以做，只需获取第一个元素，这在这里是不可能的，比如短路循环。同时，获取所有子序列比仅获取一个子序列更通用。 - Mad Physicist

@jpp。在我开始写答案之前，我确实考虑过这一点。这些问题非常相互关联，但是由于我们在这里删除元素，所以我想不出一个好的生成器，可以直接调用next或运行到完成。 - Mad Physicist

@jpp。我已更改此标题。 - Mad Physicist

Answer 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]

- Marcus.Aurelianus

---

这不是正确的。尝试使用 sub_list = [1, 2] 和 big_list = [1, 2, 1, 2]。结果应该是 []，但你得到了 [1, 2]。如果你要原地删除，你必须向后移动。 - Mad Physicist

@疯狂物理学家，更新了，通过了，你改变主意取消踩了吗？ - Marcus.Aurelianus

是的，这非常好。可以说比我的更好。 - Mad Physicist

@物理学家，谢谢您先生。 - Marcus.Aurelianus

Answer 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]

- blhsing

---

这不是超级高效的，但非常整洁。 - Mad Physicist

Answer 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

- mingganz

---

这在可读性方面没有得到改善。末尾的短子序列永远不会等于sub，而且列表足够聪明，会首先检查长度是否相等。 - Mad Physicist

你基本上是让检查变得更难读 而且 不够高效。 - Mad Physicist

如果列表'sub'很大，从性能的角度来看，我认为'if (i+sub_len) < lst_len'比'if lst[i: i+sub_len] == sub'更有效率。 'lst[i：i+sub_len]'需要生成一个列表，这将会消耗内存，对吧？ - mingganz

我想是这样的。太糟糕了，列表不允许你获取切片的视图而不是副本。+1 - Mad Physicist

Answer 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的解决方案在我的本地机器上表现得更好。

- RandomDude

Answer 6

使用 itertools.zip_longest 创建 n 个元素的元组（其中 n 是 sub_list 的长度），然后在其中一个元素匹配 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]

- Sunitha

Answer 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']

---

第三种选择 - 使用 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来将此选项转换为仅使用sequences工作，例如：def remove(seq，subsequence)：。

选项2 - 使用more_itertools

对于可迭代对象中的每个匹配子序列，都会找到相应的索引。在枚举迭代器时，如果在indices中找到了索引，则通过从迭代器中消耗下一个n-1元素来跳过其余子序列。否则，将生成一个项目。

通过运行> pip install more_itertools来安装此库。

选项3 - 使用more_itertools.replace

此工具使用谓词定义的子序列替换项目。为了删除项目，我们用空容器（例如substitutes=[]）进行替换。被替换的项目的长度由window_size参数指定（该值等于子序列的长度）。

- pylang

---

我真的不喜欢这里的 tuple(iterable)。你失去了所有惰性求值的好处，只是为了得到切片。如果你要编写一个生成器解决方案，你应该尝试将其保持与 itertools 生成器相同的标准，这样你就可以将它们钩在一起形成惰性评估管道。 - Patrick Haugh

不是，我指的是另外两个。iterable = tuple(iterable) 和 seq = tuple(iterable)。 - Patrick Haugh

啊，我明白了。我们将其转换为元组以便使用本地切片。另一个选择可能是使用itertools.islice，但这当然需要一个库。在选项1中，我提到您可以删除前两行转换为元组的代码。然后它们只能用于序列。也许我会添加一个使用itertools的选项。谢谢。 - pylang

@PatrickHaugh，感谢您的反馈。您提到“...尝试将其与itertools生成器保持相同的标准”。然而，在itertools中，tuple(iterable)并不罕见，例如在文档和示例中的组合示例。您指的是哪些标准？ - pylang

Answer 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]

这是针对在线程序员的，如果你想从库中使用一个函数，那么就用这个。

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

- Dmitry Dyachkov

Answer 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()的签名将有所不同。

- user5319825

---

很好地使用了 more_itertools。你说的“在Python3中，locate()的签名将有所不同”是什么意思？ - pylang

请参考以下链接：link - user5319825

Answer 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

基本上，当我找到子列表的每个重复项并将它们删除时，我会在找到不属于重复项的元素时将其附加到新列表中。当新列表和大列表相同时，所有重复项都已被找到，这时我就停止了。我没有使用try-except，因为我认为不应该出现任何索引错误。

这与@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中的函数来展平结果列表。此展平列表中的每个元素都是在子列表的副本中的索引。最后，我创建一个new_list，其中包含big_list中的每个具有未在展平列表中找到的索引的元素。

我认为这种方法不在其他答案中。一旦你意识到它的工作原理，它非常整洁并且非常高效（由于列表推导的性质）。

- Adi219