检查 Python 中是否存在切片列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3313590/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Check for presence of a sliced list in Python
提问by Jonathan
I want to write a function that determines if a sublist exists in a larger list.
我想编写一个函数来确定一个子列表是否存在于更大的列表中。
list1 = [1,0,1,1,1,0,0]
list2 = [1,0,1,0,1,0,1]
#Should return true
sublistExists(list1, [1,1,1])
#Should return false
sublistExists(list2, [1,1,1])
Is there a Python function that can do this?
有没有可以做到这一点的 Python 函数？
采纳答案by Mark Byers
If you are sure that your inputs will only contain the single digits 0 and 1 then you can convert to strings:
如果您确定您的输入将只包含单个数字 0 和 1，那么您可以转换为字符串：
def sublistExists(list1, list2):
return ''.join(map(str, list2)) in ''.join(map(str, list1))
This creates two strings so it is not the most efficient solution but since it takes advantage of the optimized string searching algorithm in Python it's probably good enough for most purposes.
这会创建两个字符串，因此它不是最有效的解决方案，但由于它利用了 Python 中优化的字符串搜索算法，因此对于大多数用途来说可能已经足够了。
If efficiency is very important you can look at the Boyer-Moorestring searching algorithm, adapted to work on lists.
如果效率非常重要，您可以查看适用于列表的Boyer-Moore字符串搜索算法。
A naive search has O(n*m) worst case but can be suitable if you cannot use the converting to string trick and you don't need to worry about performance.
天真的搜索有 O(n*m) 最坏的情况，但如果您不能使用转换为字符串的技巧并且不需要担心性能，则可能是合适的。
回答by sas4740
No function that I know of
没有我所知道的功能
def sublistExists(list, sublist):
for i in range(len(list)-len(sublist)+1):
if sublist == list[i:i+len(sublist)]:
return True #return position (i) if you wish
return False #or -1
As Mark noted, this is not the most efficient search (it's O(n*m)). This problem can be approached in much the same way as string searching.
正如 Mark 所指出的，这不是最有效的搜索（它是 O(n*m)）。这个问题可以用与字符串搜索大致相同的方式来解决。
回答by Nas Banov
Let's get a bit functional, shall we? :)
让我们有点功能性，好吗？:)
def contains_sublist(lst, sublst):
n = len(sublst)
return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1))
Note that any()will stop on first match of sublst within lst - or fail if there is no match, after O(m*n) ops
请注意，any()将在 lst 内 sublst 的第一次匹配时停止 - 如果没有匹配，则在 O(m*n) 操作后失败
回答by John La Rooy
Here is a way that will work for simple lists that is slightly less fragile than Mark's
这是一种适用于简单列表的方法，它比 Mark 的脆弱性稍低
def sublistExists(haystack, needle):
def munge(s):
return ", "+format(str(s)[1:-1])+","
return munge(needle) in munge(haystack)
回答by Suhail
if iam understanding this correctly, you have a larger list, like :
如果我正确理解这一点，您将拥有一个更大的列表，例如：
list_A= ['john', 'jeff', 'dave', 'shane', 'tim']
then there are other lists
然后还有其他列表
list_B= ['sean', 'bill', 'james']
list_C= ['cole', 'wayne', 'jake', 'moose']
and then i append the lists B and C to list A
然后我将列表 B 和 C 附加到列表 A
list_A.append(list_B)
list_A.append(list_C)
so when i print list_A
所以当我打印 list_A
print (list_A)
i get the following output
我得到以下输出
['john', 'jeff', 'dave', 'shane', 'tim', ['sean', 'bill', 'james'], ['cole', 'wayne', 'jake', 'moose']]
now that i want to check if the sublist exists:
现在我想检查子列表是否存在：
for value in list_A:
value= type(value)
value= str(value).strip('<>').split()[1]
if (value == "'list'"):
print "True"
else:
print "False"
this will give you 'True' if you have any sublist inside the larger list.
如果您在较大的列表中有任何子列表，这将为您提供“真”。
回答by chainet
Simply create sets from the two lists and use the issubset function:
只需从两个列表中创建集合并使用 issubset 函数：
def sublistExists(big_list, small_list):
return set(small_list).issubset(set(big_list))
回答by SuperNova
def sublistExists(x, y):
occ = [i for i, a in enumerate(x) if a == y[0]]
for b in occ:
if x[b:b+len(y)] == y:
print 'YES-- SUBLIST at : ', b
return True
if len(occ)-1 == occ.index(b):
print 'NO SUBLIST'
return False
list1 = [1,0,1,1,1,0,0]
list2 = [1,0,1,0,1,0,1]
#should return True
sublistExists(list1, [1,1,1])
#Should return False
sublistExists(list2, [1,1,1])
回答by wwii
Might as well throw in a recursive version of @NasBanov's solution
不妨抛出@NasBanov 解决方案的递归版本
def foo(sub, lst):
'''Checks if sub is in lst.
Expects both arguments to be lists
'''
if len(lst) < len(sub):
return False
return sub == lst[:len(sub)] or foo(sub, lst[1:])
回答by Martin Broadhurst
The efficient way to do this is to use the Boyer-Moore algorithm, as Mark Byers suggests. I have done it already here: Boyer-Moore search of a list for a sub-list in Python, but will paste the code here. It's based on the Wikipedia article.
正如 Mark Byers 所建议的那样，执行此操作的有效方法是使用Boyer-Moore 算法。我已经在这里完成了：Boyer-Moore search of a list for a sub-list in Python，但会将代码粘贴到此处。它基于维基百科文章。
The search()function returns the index of the sub-list being searched for, or -1 on failure.
该search()函数返回正在搜索的子列表的索引，失败时返回 -1。
def search(haystack, needle):
"""
Search list `haystack` for sublist `needle`.
"""
if len(needle) == 0:
return 0
char_table = make_char_table(needle)
offset_table = make_offset_table(needle)
i = len(needle) - 1
while i < len(haystack):
j = len(needle) - 1
while needle[j] == haystack[i]:
if j == 0:
return i
i -= 1
j -= 1
i += max(offset_table[len(needle) - 1 - j], char_table.get(haystack[i]));
return -1
def make_char_table(needle):
"""
Makes the jump table based on the mismatched character information.
"""
table = {}
for i in range(len(needle) - 1):
table[needle[i]] = len(needle) - 1 - i
return table
def make_offset_table(needle):
"""
Makes the jump table based on the scan offset in which mismatch occurs.
"""
table = []
last_prefix_position = len(needle)
for i in reversed(range(len(needle))):
if is_prefix(needle, i + 1):
last_prefix_position = i + 1
table.append(last_prefix_position - i + len(needle) - 1)
for i in range(len(needle) - 1):
slen = suffix_length(needle, i)
table[slen] = len(needle) - 1 - i + slen
return table
def is_prefix(needle, p):
"""
Is needle[p:end] a prefix of needle?
"""
j = 0
for i in range(p, len(needle)):
if needle[i] != needle[j]:
return 0
j += 1
return 1
def suffix_length(needle, p):
"""
Returns the maximum length of the substring ending at p that is a suffix.
"""
length = 0;
j = len(needle) - 1
for i in reversed(range(p + 1)):
if needle[i] == needle[j]:
length += 1
else:
break
j -= 1
return length
Here is the example from the question:
这是问题中的示例：
def main():
list1 = [1,0,1,1,1,0,0]
list2 = [1,0,1,0,1,0,1]
index = search(list1, [1, 1, 1])
print(index)
index = search(list2, [1, 1, 1])
print(index)
if __name__ == '__main__':
main()
Output:
输出：
2 -1
回答by Ashutosh K Singh
def sublist(l1,l2):
if len(l1) < len(l2):
for i in range(0, len(l1)):
for j in range(0, len(l2)):
if l1[i]==l2[j] and j==i+1:
pass
return True
else:
return False
