檢查Python中是否存在切片列表

Question

我想編寫一個函數來確定子列表是否存在於更大的列表中。

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函數？

Answer 1

如果你確信你的投入將只包含一個數字0和1，那麼你可以轉換爲字符串：

def sublistExists(list1, list2): 
    return ''.join(map(str, list2)) in ''.join(map(str, list1)) 

這將創建兩個字符串，所以它不是最有效的解決方案，但因爲它需要Python中優化的字符串搜索算法的優勢在大多數情況下可能足夠好。

如果效率非常重要，您可以查看Boyer-Moore字符串搜索算法，該算法適用於列表。

一個天真的搜索有O（n * m）最壞的情況，但可以適合，如果你不能使用轉換爲字符串技巧，你不需要擔心性能。

Answer 2

無功能，我知道

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 

正如馬克指出，這是不是最有效的搜索（它的O（N * M））。這個問題可以像字符串搜索一樣進行。

Answer 3

讓我們來看看功能，我們？ :)

def contains_sublist(lst, sublst): 
    n = len(sublst) 
    return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1)) 

注意any()將停止sublst的第一場比賽LST內 - 或者，如果沒有匹配，O（m * n個）失敗後OPS

Answer 4

這是一種方式，會爲工作簡單列出了略少脆弱比馬克的

def sublistExists(haystack, needle): 
    def munge(s): 
     return ", "+format(str(s)[1:-1])+"," 
    return munge(needle) in munge(haystack) 

Answer 5

如果IAM理解這個正確的，你有一個較大的列表，如：

list_A= ['john', 'jeff', 'dave', 'shane', 'tim'] 

名

然後還有其他名單

list_B= ['sean', 'bill', 'james'] 

list_C= ['cole', 'wayne', 'jake', 'moose'] 

，然後我追加列表B和C列出一個

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" 

這會給你「真」，如果你有更大的名單內的任何子表。

Answer 6

只需創建一個從兩個列表設置和使用issubset功能：

def sublistExists(big_list, small_list): 
    return set(small_list).issubset(set(big_list)) 

Answer 7

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]) 

Answer 8

可能會在@ 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:]) 

Answer 9

的有效途徑遞歸版本，以及拋出去正如馬克·拜爾斯建議的那樣，這是否使用Boyer-Moore algorithm。我已經在這裏做了：Boyer-Moore search of a list for a sub-list in Python，但會在這裏粘貼代碼。它基於維基百科的文章。

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 

Answer 10

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