如何测试一个列表是否包含另一个作为连续子序列的列表？

如果所有项目都是唯一的，则可以使用 set。

>>> items = set([-1, 0, 1, 2])
>>> set([1, 2]).issubset(items)
True
>>> set([1, 3]).issubset(items)
False

编辑之后:

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

这是我的版本:

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 在他的评论中指出的那样。它不对任何子列表进行切片，因此应该是相当有效的。

新手感兴趣的一点是它使用的是 For 语句上的 else 子句-这不是我经常使用的东西，但在这种情况下可以是无价的。

这与在字符串中查找子字符串相同，因此对于大型列表，实现类似于 Boyer-Moore字符串搜索算法的东西可能更有效。

注意: 如果您正在使用 Python 3，请将 xrange更改为 range。

这种方法工作起来相当快，因为它使用内建的 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

我已经尽力让这件事变得更有效率了。

它使用一个发电机，那些不熟悉这些野兽的人被建议检查 他们的文件和 屈服表达式。

基本上，它从子序列创建一个值生成器，可以通过发送一个真值来重置它。如果生成器被重置，它将从 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

下面是一个使用列表方法的简单算法:

#!/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()

我觉得这个很快。

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

如果 big列表真的很大，我可以谦虚地建议使用 Rabin-Karp 算法吗。这个链接甚至包含了几乎可用的 Python 代码。

如果我们对测试一个列表是否包含另一个作为序列的列表的问题进行细化，那么答案可能是下一个一行程序:

def contains(subseq, inseq):
return any(inseq[pos:pos + len(subseq)] == subseq for pos in range(0, len(inseq) - len(subseq) + 1))

在这里，我使用单元测试来调整这个一行程序:

Https://gist.github.com/anonymous/6910a85b4978daee137f

最小代码:

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`

有一个 all()和 any()函数来完成这项工作。 检查 big是否包含 small中的所有元素

result = all(elem in big for elem in small)

检查 small是否包含 big中的任何元素

result = any(elem in big for elem in small)

可变的结果是布尔值(TRUE/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]))

它提供了错误的输出。

这里提供的解决方案代码行较少，易于理解(或者至少我是这么认为的)。

如果你想保持顺序(只有当较小的列表在较大的列表中以相同的顺序出现时才匹配) :

def is_ordered_subset(l1, l2):
# First check to see if all element of l1 are in l2 (without checking order)
if not set(l1).issubset(l2):
return False


length = len(l1)
# Make sublist of same size than l1
list_of_sublist = [l2[i:i+length] for i, x in enumerate(l2)]
#Check if one of this sublist is l1
return l1 in list_of_sublist

Dave 的回答很好，但是我建议这个实现更多的是 有效率，而不是使用嵌套循环。

def contains(small_list, big_list):
"""
Returns index of start of small_list in big_list if big_list
contains small_list, otherwise -1.
"""
loop = True
i, curr_id_small= 0, 0
while loop and i<len(big_list):
if big_list[i]==small_list[curr_id_small]:
if curr_id_small==len(small_list)-1:
loop = False
else:
curr_id_small += 1
else:
curr_id_small = 0
i=i+1
if not loop:
return i-len(small_list)
else:
return -1

你可以使用 numpy:

def contains(l1, l2):
""" returns True if l2 conatins l1 and False otherwise """


if len(np.intersect1d(l1,l2))==len(l1):
return = True
else:
return = False

我总结并评估了不同技术所花费的时间

使用的方法有:

def containsUsingStr(sequence, element:list):
return str(element)[1:-1] in str(sequence)[1:-1]




def containsUsingIndexing(sequence, element:list):
lS, lE = len(sequence), len(element)
for i in range(lS - lE + 1):
for j in range(lE):
if sequence[i+j] != element[j]: break
else: return True
return False




def containsUsingSlicing(sequence, element:list):
lS, lE = len(sequence), len(element)
for i in range(lS - lE + 1):
if sequence[i : i+lE] == element: return True
return False




def containsUsingAny(sequence:list, element:list):
lE = len(element)
return any(element == sequence[i:i+lE] for i in range(len(sequence)-lE+1))

时间分析代码(平均超过1000次迭代) :

from time import perf_counter


functions = (containsUsingStr, containsUsingIndexing, containsUsingSlicing, containsUsingAny)
fCount = len(functions)




for func in functions:
print(str.ljust(f'Function : {func.__name__}', 32), end='   ::   Return Values: ')
print(func([1,2,3,4,5,5], [3,4,5,5]) , end=', ')
print(func([1,2,3,4,5,5], [1,3,4,5]))






avg_times = [0]*fCount
for _ in range(1000):
perf_times = []
for func in functions:
startTime = perf_counter()
func([1,2,3,4,5,5], [3,4,5,5])
timeTaken = perf_counter()-startTime
perf_times.append(timeTaken)
        



for t in range(fCount): avg_times[t] += perf_times[t]


minTime = min(avg_times)
print("\n\n Ratio of Time of Executions : ", ' : '.join(map(lambda x: str(round(x/minTime, 4)), avg_times)))

产出:

结论: 在这种情况下，切片手术被证明是最快的

下面是一个简单而有效的函数，用于检查大列表是否按照匹配顺序包含小列表:

def contains(big, small):
i = 0
for value in big:
if value == small[i]:
i += 1
if i == len(small):
return True
else:
i = 1 if value == small[0] else 0
return False

用法:

"""
>>> contains([1,2,3,4,5], [2,3,4])
True
>>> contains([4,2,3,2,4], [2,3,4])
False
>>> contains([1,2,3,2,3,2,2,4,3], [2,4,3])
True
"""