wake-up-neo.net

Testen, ob eine Liste eine andere Liste mit Python enthält

Wie kann ich testen, ob eine Liste eine andere Liste enthält (dh es handelt sich um eine zusammenhängende Untersequenz)? Angenommen, es gab eine Funktion namens

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]

Bearbeiten:

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]
41
None

Hier ist meine Version:

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

Es gibt einen Tupel von (Start, Ende + 1) zurück, da ich denke, dass dies mehr Pythonic ist, wie Andrew Jaffe in seinem Kommentar hervorhebt. Es werden keine Unterlisten erstellt, daher sollte es einigermaßen effizient sein.

Für Neulinge ist es von Interesse, dass sie die else-Klausel in der for-Anweisung verwendet - dies ist nichts, was ich sehr oft benutze, aber in solchen Situationen von unschätzbarem Wert.

Dies ist identisch mit der Suche nach Teilstrings in einem String. Daher kann es bei großen Listen effizienter sein, etwas wie den Boyer-Moore-Algorithmus zu implementieren.

16
Dave Kirby

Wenn alle Elemente eindeutig sind, können Sie Sets verwenden.

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

Dazu gibt es eine Funktion all() und any() . Um zu überprüfen, ob list1 ALLE Elemente in list2 enthält

result = all(elem in list1 for elem in list2)

Um zu überprüfen, ob list1 ANY Elemente in list2 enthält

result = any(elem in list1 for elem in list2)

das Ergebnis der Variablen wäre boolean (TRUE/FALSE).

10
ericyan3000

Darf ich demütig den Rabin-Karp-Algorithmus vorschlagen , wenn die big-Liste wirklich groß ist. Der Link enthält sogar fast verwendbaren Code in fast Python.

4
9000

Nach der Bearbeitung von 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
3
eumiro

Hier ist ein einfacher Algorithmus, der Listenmethoden verwendet:

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

Wenn wir das Problem beim Testen verfeinern, wenn eine Liste eine andere Liste mit einer Sequenz enthält, könnte die Antwort der nächste Einzeiler sein:

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

Hier haben wir Unit-Tests durchgeführt, um diesen One-Liner zu optimieren:

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

1
Oleksiy

Hier ist meine Antwort. Mit dieser Funktion können Sie herausfinden, ob B eine Unterliste von A ist. Die Komplexität der Zeit ist 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`
1
Akila D. Perera

Das funktioniert und ist ziemlich schnell, da es die lineare Suche mit der eingebauten list.index()-Methode und dem ==-Operator durchführt:

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
1
martineau

Kleinster Code:

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

Ich habe versucht, dies so effizient wie möglich zu gestalten.

Es verwendet einen Generator; Denjenigen, die mit diesen Tieren nicht vertraut sind, wird empfohlen, ihre Dokumentation und die von Flood-Ausdrücken zu überprüfen.

Im Grunde erstellt es aus der Untersequenz einen Generator von Werten, der durch Senden eines echten Werts zurückgesetzt werden kann. Wenn der Generator zurückgesetzt wird, gibt er ab dem Beginn von sub wieder nach.

Dann werden nur aufeinanderfolgende Werte von sequence mit den Generatorerträgen verglichen und der Generator zurückgesetzt, falls sie nicht übereinstimmen.

Wenn der Generator keine Werte mehr hat, d. H. Das Ende von sub erreicht hat, ohne zurückgesetzt zu werden, bedeutet dies, dass wir unsere Übereinstimmung gefunden haben.

Da es für jede Sequenz funktioniert, können Sie es sogar für Strings verwenden. In diesem Fall verhält es sich ähnlich wie str.find, außer dass es False anstelle von -1 zurückgibt.

Eine weitere Anmerkung: Ich denke, dass der zweite Wert des zurückgegebenen Tuples gemäß den Python-Standards normalerweise um einen höheren Wert liegen sollte. d.h. "string"[0:2] == "st". Aber die Spezifikation sagt etwas anderes, so funktioniert das.

Es hängt davon ab, ob es sich um eine allgemeine Routine handelt oder ob ein bestimmtes Ziel implementiert wird. Im letzteren Fall ist es möglicherweise besser, eine Allzweckroutine zu implementieren und sie dann in eine Funktion einzuhüllen, die den Rückgabewert an die Spezifikation anpasst.

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
0
intuited

Das Problem der meisten Antworten ist, dass sie für einzigartige Elemente in der Liste gut sind. Wenn Elemente nicht eindeutig sind und Sie dennoch wissen möchten, ob es eine Kreuzung gibt, sollten Sie Elemente zählen:

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

Sie können die Kreuzung auch mit ''.join(list1&list2) zurückgeben.

0
mafonya

Ich denke, das ist schnell ...

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
0
ChessMaster