如何测试一个列表是否包含另一个列表(即它是一个连续的子序列)。说有一个函数叫包含。
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
它返回一个(start, end+1)的元组,因为我认为这更像pythonic,正如Andrew Jaffe在他的评论中指出的那样。 它没有切分任何子列表,所以应该是相当高效的。
对于新手来说,有一点值得关注,那就是它使用了 否则子句 - 这不是我经常使用的东西,但在这样的情况下是非常宝贵的。
这和在字符串中查找子串是一样的,所以对于大的列表,实现类似于 Boyer-Moore算法.
如果所有的项目都是唯一的,你可以使用套装。
>>> items = set([-1, 0, 1, 2])
>>> set([1, 2]).issubset(items)
True
>>> set([1, 3]).issubset(items)
False
有一个 all()
和 any()
函数来完成这个任务。big
中包含的所有元素 small
result = all(elem in big for elem in small)
检查是否 small
中包含任何元素 big
result = any(elem in big for elem in small)
变量结果将是布尔值(TRUEFALSE)。
请允许我谦虚地建议 拉宾-卡普算法 如果 big
列表真的很大。链接中甚至包含了几乎可以用几乎python的代码。
经过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
这个可以用,而且速度相当快,因为它使用内置的 list.index()
方法和 ==
操作符。
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
这是一个使用列表方法的直接算法。
#!/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 是否包含另一个 list 的序列,答案可能是下一个单行本。
def contains(subseq, inseq):
return any(inseq[pos:pos + len(subseq)] == subseq for pos in range(0, len(inseq) - len(subseq) + 1))
这里是我用来调整这个单行道的单元测试。
最小的代码。
def contains(a,b):
str(a)[1:-1].find(str(b)[1:-1])>=0
这是我的答案 这个函数将帮助你找出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`
我试图让它尽可能的高效。
它使用了一个生成器;不熟悉这些兽类的人建议检查一下 其文件 以及 屈服表达式.
基本上,它从子序列中创建了一个值的生成器,可以通过发送一个真值来重置它。 如果生成器被重置,它就会重新从 sub
.
然后它只是比较连续的 sequence
与生成器的产量,如果不匹配则重置生成器。
当生成器的值用完时,即达到了最后的 sub
而不被重置,这意味着我们已经找到了我们的匹配。
由于它适用于任何序列,你甚至可以在字符串上使用它,在这种情况下,它的行为类似于 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
大多数答案的问题在于,它们只适用于列表中唯一的项目。如果项目不是唯一的,而你仍然想知道是否有交集,你应该对项目进行计数。
from collections import Counter as count
def listContains(l1, l2):
list1 = count(l1)
list2 = count(l2)
return list1&list2 == list1
print( listContains([1,1,2,5], [1,2,3,5,1,2,1]) ) # Returns True
print( listContains([1,1,2,8], [1,2,3,5,1,2,1]) ) # Returns False
你也可以通过使用 ''.join(list1&list2)
a=[[1,2] , [3,4] , [0,5,4]]
print(a.__contains__([0,5,4]))
它提供真实的输出。
a=[[1,2] , [3,4] , [0,5,4]]
print(a.__contains__([1,3]))
它提供假输出。