Cum se testează dacă o listă conține o altă listă? (Programare, Python, Lista, Conține, Compararea Listelor)

Aici este versiunea mea:

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

Acesta returnează un tuple de (start, end+1), deoarece cred că este mai pythonic, așa cum Andrew Jaffe subliniază în comentariul său. Nu feliază nicio sublistă, deci ar trebui să fie rezonabil de eficient.

Un punct de interes pentru începători este faptul că utilizează clauza else în declarația for – nu este un lucru pe care îl folosesc foarte des, dar poate fi de neprețuit în situații ca aceasta.

Acest lucru este identic cu găsirea de subșiruri într-un șir de caractere, astfel încât pentru listele mari ar putea fi mai eficient să se implementeze ceva de genul algoritmul Boyer-Moore.

Dacă toate elementele sunt unice, puteți utiliza seturi.

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

Există un all() și any() pentru a face acest lucru.Pentru a verifica dacă big conține TOATE elementele din small

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

Pentru a verifica dacă small conține TOATE elementele din big

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

variabila rezultat ar fi booleană (TRUE/FALSE).

Pot să sugerez cu umilință algoritmul Rabin-Karp în cazul în care big lista este foarte mare. Linkul conține chiar și un cod aproape utilizabil în aproape-Python.

Acest lucru funcționează și este destul de rapid, deoarece face căutarea liniară folosind builtinul list.index() și == operator:

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

După editarea lui OP:

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

Iată un algoritm simplu care folosește metode de listă:

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

Dacă rafinăm problema vorbind despre testarea dacă o listă conține o altă listă cu ca secvență, răspunsul ar putea fi următorul one-liner:

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

Iată testele unitare pe care le-am folosit pentru a pune la punct acest one-liner:

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

Cel mai mic cod:

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

Iată răspunsul meu. Această funcție vă va ajuta să aflați dacă B este o sub-listă a lui A. Complexitatea în timp este 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`

a=[[1,2] , [3,4] , [0,5,4]]
print(a.__contains__([0,5,4]))

Oferă o ieșire adevărată.

a=[[1,2] , [3,4] , [0,5,4]]
print(a.__contains__([1,3]))

Oferă o ieșire falsă.

Am încercat să fac această funcție cât mai eficientă posibil.

Folosește un generator; cei care nu sunt familiarizați cu aceste bestii sunt sfătuiți să verifice documentația lor și pe cea a expresii de randament.

Practic, acesta creează un generator de valori din subsecvența care poate fi resetat prin trimiterea unei valori adevărate. În cazul în care generatorul este resetat, începe să producă din nou randamente de la începutul secvenței sub.

Apoi, se compară pur și simplu valorile succesive ale sequence cu randamentele generatorului, resetând generatorul dacă acestea nu corespund.

Atunci când generatorul rămâne fără valori, adică ajunge la sfârșitul lui sub fără a fi resetat, înseamnă că am găsit o potrivire.

Deoarece funcționează pentru orice secvență, îl puteți utiliza chiar și pentru șiruri de caractere, caz în care se comportă în mod similar cu str.find, cu excepția faptului că returnează False în loc de -1.

Ca o notă suplimentară: cred că a doua valoare a tuplei returnate ar trebui, în conformitate cu standardele Python, să fie în mod normal cu o valoare mai mare cu unu. de exemplu "string"[0:2] == "st". Dar specificația spune altceva, așa că așa funcționează.

Depinde dacă aceasta este menită să fie o rutină de uz general sau dacă implementează un obiectiv specific; în acest din urmă caz, ar fi mai bine să se implementeze o rutină de uz general și apoi să se înfășoare într-o funcție care să modifice valoarea returnată pentru a se potrivi cu specificațiile.

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

Cred că aceasta este rapidă…

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

Problema majorității răspunsurilor, că sunt bune pentru elemente unice în listă. Dacă elementele nu sunt unice și totuși doriți să știți dacă există o intersecție, ar trebui să numărați elementele:

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

De asemenea, puteți returna intersecția folosind ''.join(list1&list2)

Iată o soluție cu mai puține linii de cod și ușor de înțeles (sau cel puțin așa îmi place să cred).

Dacă doriți să păstrați ordinea (să vă potriviți numai dacă lista mai mică se găsește în aceeași ordine în lista mai mare):

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 

Răspunsul lui Dave este bun. Dar vă sugerez această implementare care este mai eficientă și nu folosește bucle imbricate.

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