从列表中移除子列表。

Question

我想在Python中实现以下功能：

A = [1, 2, 3, 4, 5, 6, 7, 7, 7]
C = A - [3, 4]  # Should be [1, 2, 5, 6, 7, 7, 7]
C = A - [4, 3]  # Should not be removing anything, because sequence 4, 3 is not found

所以，我只想从另一个列表中删除一个子列表的第一次出现（作为序列）。我该怎么做？

编辑：我是在谈论列表而不是集合。这意味着项的顺序（序列）很重要（在A和B中都重要），并且重复项也很重要。

- dimitris93

---

这甚至没有意义，我想你的意思是 A - B。 - Netwave

顺序重要吗？如果 A = [1, 2, 3, 4, 5, 6, 7, 3, 8, 5, 4]，输出是什么？ - pault

当有多个匹配项时，是删除所有还是只删除第一个匹配项？ - Sphinx

@pault 顺序和重复很重要。 - dimitris93

@Sphinx 只匹配第一个。我更新了我的问题。显然有很多事情不清楚。 - dimitris93

Answer 1

使用集合：

C = list(set(A) - set(B))

如果您想保留重复项和/或顺序：

filter_set = set(B)
C = [x for x in A if x not in filter_set]

- Netwave

---

这不会保留重复项，对吗？ - dimitris93

看看我更新后的问题。我谈论的是列表，而不是集合。顺序也很重要。 - dimitris93

这将不会维护元素的原始顺序。可以尝试类似于 [i for i in A if i not in B] 的操作。 - Feng

@Netwave 我的解决方案不需要将它变成一个集合。 - Feng

这些答案都不适用于B=[4,3]，正如原帖中所说的那样，它不应该删除任何内容。感谢这些答案，因为它们会帮助那些试图以简单明了的方式从列表中删除值的人们。 - Martin

Answer 2

如果您想要删除确切的序列，这里有一种方法：

通过检查子列表是否与所需序列匹配来找到不良索引：

bad_ind = [range(i,i+len(B)) for i,x in enumerate(A) if A[i:i+len(B)] == B]
print(bad_ind)
#[[2, 3]]

由于这返回一个列表的列表，因此需要将其扁平化并转换为集合：

bad_ind_set = set([item for sublist in bad_ind for item in sublist])
print(bad_ind_set)
#set([2, 3])

现在使用此集合按索引过滤您的原始列表：

C = [x for i,x in enumerate(A) if i not in bad_ind_set]
print(C)
#[1, 2, 5, 6, 7, 7, 7]

上述的`bad_ind_set`将会移除所有匹配的序列。如果你只想移除第一个匹配，那就更简单了。你只需要使用`bad_ind`的第一个元素即可（不需要展开列表）：

bad_ind_set = set(bad_ind[0])

更新：以下是使用短路的 for 循环查找和删除第一个匹配子序列的方法。这种方法速度更快，因为它在找到第一个匹配项后就会停止循环。

start_ind = None
for i in range(len(A)):
    if A[i:i+len(B)] == B:
        start_ind = i
        break

C = [x for i, x in enumerate(A) 
     if start_ind is None or not(start_ind <= i < (start_ind + len(B)))]
print(C)
#[1, 2, 5, 6, 7, 7, 7]

- pault

---

我在思考这个问题与子字符串查询类似，为什么不考虑像KMP等一种解决方案呢？ - Sphinx

Answer 3

我认为这个问题就像一个子字符串搜索，因此可以应用子字符串搜索算法，如KMP、BM等。即使您想支持多个模式，也有一些多模式算法，如Aho-Corasick、Wu-Manber等。

下面是来自GitHub Gist的Python实现的KMP算法。 注：作者不是我。我只是想分享我的想法。

class KMP:
    def partial(self, pattern):
        """ Calculate partial match table: String -> [Int]"""
        ret = [0]

        for i in range(1, len(pattern)):
            j = ret[i - 1]
            while j > 0 and pattern[j] != pattern[i]:
                j = ret[j - 1]
            ret.append(j + 1 if pattern[j] == pattern[i] else j)
        return ret

    def search(self, T, P):
        """
        KMP search main algorithm: String -> String -> [Int]
        Return all the matching position of pattern string P in S
        """
        partial, ret, j = self.partial(P), [], 0

        for i in range(len(T)):
            while j > 0 and T[i] != P[j]:
                j = partial[j - 1]
            if T[i] == P[j]: j += 1
            if j == len(P):
                ret.append(i - (j - 1))
                j = 0

        return ret

然后使用它来计算出匹配的位置，最后移除匹配：

A = [1, 2, 3, 4, 5, 6, 7, 7, 7, 3, 4]
B = [3, 4]
result = KMP().search(A, B)
print(result)
#assuming at least one match is found
print(A[:result[0]:] + A[result[0]+len(B):])

输出：

[2, 9]
[1, 2, 5, 6, 7, 7, 7, 3, 4]
[Finished in 0.201s]

附注：您也可以尝试其他算法。@Pault的答案足够好，除非您非常关心性能。

- Sphinx

Answer 4

使用numpy：

import numpy as np
A = [1, 2, 3, 4, 5, 6, 7, 7, 7]
B = [3,4]
C = [4,3]
list(np.setdiff1d(A,B, assume_unique=True))
output: [1, 2, 5, 6, 7, 7, 7]
list(np.setdiff1d(A,C, assume_unique=True))
output: [1, 2, 5, 6, 7, 7, 7]

- Sam S.

Answer 5

这里有另一种方法：

# Returns that starting and ending point (index) of the sublist, if it exists, otherwise 'None'.

def findSublist(subList, inList):
    subListLength = len(subList)
    for i in range(len(inList)-subListLength):
        if subList == inList[i:i+subListLength]:
            return (i, i+subListLength)
    return None


# Removes the sublist, if it exists and returns a new list, otherwise returns the old list.

def removeSublistFromList(subList, inList):
    indices = findSublist(subList, inList)
    if not indices is None:
        return inList[0:indices[0]] + inList[indices[1]:]
    else:
        return inList


A = [1, 2, 3, 4, 5, 6, 7, 7, 7]

s1 = [3,4]
B = removeSublistFromList(s1, A)
print(B)

s2 = [4,3]
C = removeSublistFromList(s2, A)
print(C)

- Vasilis G.

---

谢谢，你刚才写成了s1，但是你想说的是C = removeSublistFromList(s2, A)，这个在结尾处。 - Martin