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

Nici unul a intrebat.

Cum pot testa dacă o listă conține o altă listă (adică dacă este o subsecvență contiguă). Să zicem că există o funcție numită contains:

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]

Comentarii

  • Pentru ceea ce merită, returnând [start, end+1] este mai pythonic, deoarece arată ca o felie… (end+1)-start dă lungimea a ceea ce se găsește. –  > Por Andrew Jaffe.
  • Aceasta pare a fi o proiectare proastă – uneori funcția returnează un bool, alteori returnează o listă. Acest lucru o face foarte greu de utilizat, deoarece trebuie să verificați tipul returnat înainte de a putea face ceva cu rezultatul. IMHO o funcție numită „conține” ar trebui să returneze doar True sau False. –  > Por Dave Kirby.
  • Este oarecum trist că listele nu au încorporată funcționalitatea necesară, dar șirurile de caractere o au (str.find). –  > Por Jochen Ritzel.
  • De ce ar returna, din orice motiv, o listă și nu un tupluplu!? –  > Por Grant Paul.
  • înrudite: Cel mai bun mod de a determina dacă o secvență se află într-o altă secvență în Python –  > Por jfs.
16 răspunsuri
Dave Kirby

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.

Comentarii

  • +1 pentru nota despre algoritmii eficienți de căutare a șirurilor de caractere. Un dezavantaj al tău este adăugarea unei bucle interioare interpretate (compararea feliilor este, îmi imaginez, mai rapidă, deși copia ar putea compensa acest lucru). Voi încerca o comparație de performanță. –  > Por Tim Yates.
  • În urma unor teste suplimentare, a dvs. este cel mai bun până acum pentru subsecvențe mari. Eu aș alege-o, chiar și în ciuda micului dezavantaj pe care îl are pe seturi de date mai mici. –  > Por Tim Yates.
  • +1: Nu știam despre for‘s else clauză! Chiar astăzi am creat o construcție ciudată care implică setarea unui boolean pentru a face exact acest lucru. –  > Por mk12.
Thomas O

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

Comentarii

  • nu asta caută op –  > Por SilentGhost.
  • Tot nu va funcționa, chiar dacă toate elementele sunt unice, dacă nu sunt, de asemenea, în aceeași ordine, fără elemente întrepătrunse. de exemplu, găsind [1, 3] sau [2, 1] în [1, 2, 3] va da un rezultat fals pozitiv. Presupunând că suntem în căutarea secvenței în sine și nu doar a valorilor conținute în secvență. –  > Por intuit.
  • Cred că este mai bine să arăți cum o idee poate fi greșită (pentru a o evita pe viitor), decât să o ștergi complet. –  > Por Thomas O.
  • 22

  • Da, mai ales că aceasta este soluția corectă pentru unii oameni (ca mine) care găsesc această pagină, cărora nu le pasă de secvență. –  > Por mk12.
  • Notă pentru telespectator: rezultatele furnizate în acest exemplu nu sunt corecte. Acestea fiind spuse, acest exemplu m-a ajutat. –  > Por pangyuteng.
ericyan3000

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

Comentarii

  • Dacă nu mă înșel all(elem in list1 for elem in list2) testează toate elementele din lista2 în raport cu elementele din lista1, deci este invers. Astfel se verifică dacă lista2 conține toate elementele din lista1 –  > Por rifle2000.
9000

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.

martineau

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

Comentarii

  • Nu sunt sigur dacă există un defect puteți matineau verifica de două ori. Am încercat print (contains((1,2,3),(1,2,3))) și am obținut [0,2] în loc de [0,1,2] –  > Por user-asterix.
  • @user-asterix: Funcția returnează efectiv [start, end] așa cum a fost proiectată (și cum dorește OP). –  > Por martineau.
eumiro

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

Comentarii

  • Dar nu reușește cu contains([1,2], [-1, 0, 1, 1, 1, 2]) care returnează [2,4] în loc de ceea ce presupun că este așteptat [3,4] –  > Por Andrew Dalke.
  • Acest lucru va fi îngrozitor de ineficient pentru listele mari, deoarece creează și distruge în mod constant liste temporare de fiecare dată când face big[i:i+len(small)] –  > Por Dave Kirby.
  • @Dave: ai cronometrat acest lucru față de soluția ta? –  > Por SilentGhost.
  • Conform testelor mele, aceasta are o performanță ușor mai bună decât soluția lui Dave Kirby, chiar și pe liste mari (1 milion de elemente, cu subsetul de potrivire la sfârșit): 4,1s pentru 10 repetări față de 5,6s pentru soluția lui Dave. Mi-ar plăcea să postez codul meu de testare, dar nu există o modalitate ușoară de a face acest lucru. –  > Por Tim Yates.
  • UPDATE: Am vorbit prea repede – listele mele mici erau prea mici. Acest algoritm a explodat odată ce am mărit dimensiunea lor la 1000, în timp ce celelalte au rămas constante. Se pare că, până la urmă, Dave Kirby câștigă pentru listele mari. pastebin.com/NZwU6PUx –  > Por Tim Yates.
jfs

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

Oleksiy

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

Comentarii

  • Cred că acesta este răspunsul pentru mine! Frumos one-liner, pare corect. –  > Por hwjp.
  • întâmplător, cred că return True ar putea trece toate testele unitare. –  > Por hwjp.
Bart Mensfort

Cel mai mic cod:

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

Akila D. Perera

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`

Sihat Afnan
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ă.

intuit

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

Comentarii

  • Un efort curajos, dar aceasta are performanțe mai slabe decât soluțiile lui eumiro sau Dave Kirby. 8,2s pe benchmark-ul pe care l-am descris în celelalte comentarii. –  > Por Tim Yates.
  • Interesant de văzut diferența de viteză pentru codul nativ. Se pare că acest algoritm ar fi relativ mai rapid pentru subsecvențe mai lungi… cât de lungă a fost/s-au fost subsecvența/sub-secvențele pe care le-ați folosit în test? –  > Por intuited.
  • Aveți dreptate. Aceasta a funcționat mult mai bine decât soluția lui eumiro cu subsecvențe mai mari, dar tot nu a funcționat la fel de bine ca cea a lui Dave. –  > Por Tim Yates.
ChessMaster

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

mafonya

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)

thibaultbl

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 

HLeb

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