在Python中检查是否存在切片列表
我想写一个函数来确定一个子列表是否存在于一个更大的列表中。
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]) 有没有可以做到这一点的Python函数？
如果你确定你的input只包含单个数字0和1，那么你可以转换为string：
def sublistExists(list1, list2): return ''.join(map(str, list2)) in ''.join(map(str, list1))
这创build了两个string，所以它不是最有效的解决scheme，但是因为它利用了Python中优化的stringsearchalgorithm，所以对于大多数目的来说可能是足够好的。
如果效率非常重要，您可以查看Boyer-Moorestringsearchalgorithm，该algorithm适用于列表。
一个天真的search有O（n * m）最坏的情况，但如果你不能使用转换为string技巧，你可以适合，你不必担心性能。
让我们来点function吧？ 🙂
def contains_sublist(lst, sublst): n = len(sublst) return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1))
请注意， any()将在lst中的sublst的第一次匹配时停止 – 或者在O（m * n）ops之后没有匹配时失败
没有我知道的function
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
正如马克指出的，这不是最有效的search（它是O（n * m））。 这个问题可以像stringsearch一样进行。
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])
正如马克·拜尔斯（Mark Byers）所build议的那样，这样做的有效方法是使用Boyer-Moorealgorithm 。 我已经在这里完成了： Boyer-Moore在Python中search一个子列表的列表 ，但是会在这里粘贴代码。 它基于维基百科的文章。
search()函数返回正在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
这个问题的例子是：
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()
输出：
2 -1
这是一种适用于简单列表的方法，它比Mark的稍微脆弱
def sublistExists(haystack, needle): def munge(s): return ", "+format(str(s)[1:-1])+"," return munge(needle) in munge(haystack)
不妨投入一个@ NasBanov解决scheme的recursion版本
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:])
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
如果我正确理解这一点，你有一个更大的名单，如：
list_A= ['john', 'jeff', 'dave', 'shane', 'tim']
那么还有其他的列表
list_B= ['sean', 'bill', 'james'] list_C= ['cole', 'wayne', 'jake', 'moose']
然后我将列表B和C附加到列表A中
list_A.append(list_B) list_A.append(list_C)
所以当我打印list_A
print (list_A)
我得到以下输出
['john', 'jeff', 'dave', 'shane', 'tim', ['sean', 'bill', 'james'], ['cole', 'wayne', 'jake', 'moose']]
现在我想检查子列表是否存在：
for value in list_A: value= type(value) value= str(value).strip('<>').split()[1] if (value == "'list'"): print "True" else: print "False"
如果在更大的列表中有任何子列表，这会给你“真”。
只需从两个列表中创build集合并使用issubset函数：
def sublistExists(big_list, small_list): return set(small_list).issubset(set(big_list))
