如何从列表中删除每个出现的子列表

Question

我有两个清单:

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

我想删除big_list中的所有sub_list事件.

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

对于字符串,您可以使用此:

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

但AFAIK这对列表不起作用.

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

更新:为简单起见,我在此示例中使用了整数.但列表项可以是任意对象.

UPDATE2:

如果big_list = [1, 2, 1, 2, 1]和sub_list = [1, 2, 1],我希望结果是[2, 1](像'12121'.replace('121', ''))

UPDATE3:

我不喜欢将StackOverflow中的源代码复制+粘贴到我的代码中.这就是我在软件建议中提出第二个问题的原因:https://softwarerecs.stackexchange.com/questions/51273/library-to-remove-every-occurrence-of-sub-list-from-list-python

Update4:如果您知道要进行此方法调用的库,请将其写为答案,因为这是我首选的解决方案.

测试应通过此测试:

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

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]

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]

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]

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

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)

更新

我的第一个解决方案有一个bug.能够修复它(更新我上面的代码),但该方法现在看起来更复杂.在性能方面,它仍然比我在本地机器上的Mad Physicist的解决方案更好.

Answer 6

使用itertools.zip_longest来创建N元素的元组(其中n是SUB_LIST的长度),然后过滤当前元素和下一个n-1个元件当该元件中的一个相匹配的SUB_LIST

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

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

选项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,因此每次匹配跳过两次.

注意,您可以通过删除前两个元组分配并用例如替换参数来转换此选项以单独使用序列.iterableseqdef remove(seq, subsequence):

选项2 - 与 more_itertools

在迭代中为每个匹配的子序列定位索引.在迭代枚举迭代器时,如果找到索引indices,则通过使用n-1迭代器中的下一个元素来跳过剩余的子序列.否则,产生一个项目.

通过安装此库> pip install more_itertools.

选项3 - 用more_itertools.replace:

此工具用替换值替换谓词中定义的项的子序列.要删除项目,我们替换空容器,例如substitutes=[].替换项的长度由window_size参数指定(该值等于子序列的长度).