testing一个列表是否包含另一个Python列表
我如何testing一个列表是否包含另一个列表（即它是一个子序列）。 说有一个叫做contains的函数：
contains([1,2], [-1, 0, 1, 2]) # Returns [2, 3] (contains returns [start, end]) contains([1,3], [-1, 0, 1, 2]) # Returns False contains([1, 2], [[1, 2], 3) # Returns False contains([[1, 2]], [[1, 2], 3]) # Returns [0, 0] 编辑：
contains([2, 1], [-1, 0, 1, 2]) # Returns False contains([-1, 1, 2], [-1, 0, 1, 2]) # Returns False contains([0, 1, 2], [-1, 0, 1, 2]) # Returns [1, 3]
这是我的版本：
def contains(small, big): for i in xrange(len(big)-len(small)+1): for j in xrange(len(small)): if big[i+j] != small[j]: break else: return i, i+len(small) return False
正如Andrew Jaffe在他的评论中指出的那样，它会返回一个（start，end + 1）的元组，因为我认为这更加pythonic。 它不分片任何子列表，所以应该是合理的效率。
新手感兴趣的一点是，它使用for语句中的else子句 – 这不是我经常使用的东西，但在这样的情况下可能是非常宝贵的。
这与在string中查找子string是一样的，所以对于大的列表来说，实现类似Boyer-Moorealgorithm的效率会更高。
如果所有项目都是唯一的，则可以使用集合。
>>> items = set([-1, 0, 1, 2]) >>> set([1, 2]).issubset(items) True >>> set([1, 3]).issubset(items) False
在OP的编辑之后：
def contains(small, big): for i in xrange(1 + len(big) - len(small)): if small == big[i:i+len(small)]: return i, i + len(small) - 1 return False
如果big名单真的很大，我可以虚心地build议Rabin-Karpalgorithm 。 该链接甚至包含几乎可用的代码。
这是一个简单的使用列表方法的algorithm：
#!/usr/bin/env python def list_find(what, where): """Find `what` list in the `where` list. Return index in `where` where `what` starts or -1 if no such index. >>> f = list_find >>> f([2, 1], [-1, 0, 1, 2]) -1 >>> f([-1, 1, 2], [-1, 0, 1, 2]) -1 >>> f([0, 1, 2], [-1, 0, 1, 2]) 1 >>> f([1,2], [-1, 0, 1, 2]) 2 >>> f([1,3], [-1, 0, 1, 2]) -1 >>> f([1, 2], [[1, 2], 3]) -1 >>> f([[1, 2]], [[1, 2], 3]) 0 """ if not what: # empty list is always found return 0 try: index = 0 while True: index = where.index(what[0], index) if where[index:index+len(what)] == what: return index # found index += 1 # try next position except ValueError: return -1 # not found def contains(what, where): """Return [start, end+1] if found else empty list.""" i = list_find(what, where) return [i, i + len(what)] if i >= 0 else [] #NOTE: bool([]) == False if __name__=="__main__": import doctest; doctest.testmod()
这工作，是相当快，因为它使用内置的list.index()方法和==运算符进行线性search：
def contains(sub, pri): M, N = len(pri), len(sub) i, LAST = 0, M-N+1 while True: try: found = pri.index(sub[0], i, LAST) # find first elem in sub except ValueError: return False if pri[found:found+N] == sub: return [found, found+N-1] else: i = found+1
如果我们在讨论testing问题时将问题细化，如果一个列表包含另一个列表作为一个序列，那么答案可能是下一个单行程：
def contains(subseq, inseq): return any(inseq[pos:pos + len(subseq)] == subseq for pos in range(0, len(inseq) - len(subseq) + 1))
我在这里用unit testing来调整这个单线程：
我试图尽可能提高效率。
它使用一个发生器; build议那些不熟悉这些野兽的人检查他们的文件和产量expression式 。
基本上它创build了一个从子序列中产生的值，可以通过发送一个真值来重置。 如果发生器复位，则从sub开始处再次开始屈服。
然后，它只是比较sequence连续值与发电机产量，如果它们不匹配，则重置发电机。
当发生器用完数值时，即达到sub结束而不被重置，这意味着我们已经find了我们的匹配。
由于它适用于任何序列，所以甚至可以在string上使用它，在这种情况下，它的行为与str.find类似，不同的是它返回False而不是-1 。
作为进一步的说明：我认为返回的元组的第二个值应该符合Python标准，通常要高一个。 即"string"[0:2] == "st" 。 但规范说，否则，所以这是如何工作的。
这取决于这是为了成为一个通用的例程，还是要实现某个特定的目标; 在后一种情况下，实现一个通用的例程，然后将其包装在一个函数中可能会更好，该函数将返回值调整为符合规范。
def reiterator(sub): """Yield elements of a sequence, resetting if sent ``True``.""" it = iter(sub) while True: if (yield it.next()): it = iter(sub) def find_in_sequence(sub, sequence): """Find a subsequence in a sequence. >>> find_in_sequence([2, 1], [-1, 0, 1, 2]) False >>> find_in_sequence([-1, 1, 2], [-1, 0, 1, 2]) False >>> find_in_sequence([0, 1, 2], [-1, 0, 1, 2]) (1, 3) >>> find_in_sequence("subsequence", ... "This sequence contains a subsequence.") (25, 35) >>> find_in_sequence("subsequence", "This one doesn't.") False """ start = None sub_items = reiterator(sub) sub_item = sub_items.next() for index, item in enumerate(sequence): if item == sub_item: if start is None: start = index else: start = None try: sub_item = sub_items.send(start is None) except StopIteration: # If the subsequence is depleted, we win! return (start, index) return False
我觉得这个很快…
def issublist(subList, myList, start=0): if not subList: return 0 lenList, lensubList = len(myList), len(subList) try: while lenList - start >= lensubList: start = myList.index(subList[0], start) for i in xrange(lensubList): if myList[start+i] != subList[i]: break else: return start, start + lensubList - 1 start += 1 return False except: return False
最小的代码：
def contains(a,b): str(a)[1:-1].find(str(b)[1:-1])>=0
这是我的解决scheme。 这个函数将帮助你找出B是否是A的子列表。时间复杂度是O（n）。
def does_A_contain_B(A, B): #remember now A is the larger list b_size = len(B) for a_index in range(0, len(A)): if A[a_index : a_index+b_size]==B: return True else: return False
