Kiểm tra xem danh sách có chứa danh sách khác với Python

Question

Làm cách nào để kiểm tra xem danh sách có chứa danh sách khác hay không (nghĩa là đó là một chuỗi). Giả sử có một chức năng gọi là chứa:

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] 

Edit:

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] 

Answer 1

Đây là phiên bản của tôi:

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 

Nó trả về một tuple của (bắt đầu, kết thúc + 1) kể từ khi tôi nghĩ rằng đó là pythonic hơn, như Andrew Jaffe chỉ ra trong bình luận của mình. Nó không cắt bất kỳ danh sách con nào nên có hiệu quả hợp lý.

Một điểm đáng quan tâm đối với người mới sử dụng là nó sử dụng else clause on the for statement - đây không phải là điều tôi thường sử dụng nhưng có thể vô giá trong các tình huống như thế này.

Điều này giống hệt với việc tìm kiếm các chất nền trong một chuỗi, vì vậy đối với các danh sách lớn, việc thực hiện một cái gì đó giống như Boyer-Moore algorithm có hiệu quả hơn.

Answer 2

Nếu tất cả các mục là duy nhất, bạn có thể sử dụng bộ.

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

Answer 3

Sau khi chỉnh sửa OP của:

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 

Answer 4

này hoạt động và khá nhanh kể từ khi nó hiện tìm kiếm tuyến tính bằng cách sử dụng được xây dựng trong list.index() phương pháp và == điều hành:

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 

Answer 5

Tôi cố gắng để thực hiện điều này hiệu quả càng tốt.

Sử dụng trình tạo; những người không quen thuộc với những con thú này nên kiểm tra their documentation và của yield expressions.

Về cơ bản, nó tạo ra một trình tạo các giá trị từ chuỗi có thể được đặt lại bằng cách gửi nó một giá trị thực. Nếu máy phát lại được đặt lại, nó sẽ bắt đầu lại từ đầu sub.

Sau đó, nó chỉ so sánh các giá trị kế tiếp của sequence với năng suất máy phát, đặt lại trình tạo nếu chúng không khớp.

Khi máy phát hết giá trị, nghĩa là đến cuối sub mà không bị đặt lại, điều đó có nghĩa là chúng tôi đã tìm thấy kết quả phù hợp.

Vì nó hoạt động cho bất kỳ chuỗi nào, bạn thậm chí có thể sử dụng nó trên chuỗi, trong trường hợp nó hoạt động tương tự như str.find, ngoại trừ nó trả về False thay vì -1.

Lưu ý thêm: Tôi nghĩ rằng giá trị thứ hai của bộ trả về phải phù hợp với tiêu chuẩn Python, thường là cao hơn. tức là "string"[0:2] == "st". Nhưng spec nói khác, vì vậy đó là cách làm việc này.

Nó phụ thuộc vào việc này có phải là một thói quen có mục đích chung hay không hoặc nó có thực hiện một số mục tiêu cụ thể hay không; trong trường hợp sau nó có thể tốt hơn để thực hiện một thói quen có mục đích chung và sau đó bọc nó trong một chức năng mà twiddles giá trị trả lại cho phù hợp với spec.

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 

Answer 6

Dưới đây là một thuật toán đơn giản có sử dụng phương pháp danh sách:

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

Answer 7

Tôi nghĩ rằng đây là một trong nhanh ...

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 

Answer 8

Có thể tôi một cách khiêm nhường đề nghị Rabin-Karp algorithm nếu danh sách big là thực sự lớn. Liên kết thậm chí còn chứa mã gần như có thể sử dụng trong hầu hết Python.

Answer 9

Nếu chúng ta tinh chỉnh các vấn đề nói về việc kiểm tra xem một danh sách chứa một danh sách với như là một chuỗi, câu trả lời có thể là sau một liner:

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

đây kiểm tra đơn vị tôi đã sử dụng để điều chỉnh lên một này -liner:

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

Answer 10

đang nhỏ nhất:

def contains(a,b): 
    str(a)[1:-1].find(str(b)[1:-1])>=0 

Answer 11

Đây là giải pháp của tôi. Chức năng này sẽ giúp bạn tìm hiểu xem B là một danh sách phụ của A. Độ phức tạp thời gian là 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