Prüfen, ob zwei ungeordnete Listen gleich sind

Question

Ich suche nach einer einfachen (und schnellen) Methode, um festzustellen, ob zwei ungeordnet Listen enthalten dieselben Elemente:

Zum Beispiel:

['one', 'two', 'three'] == ['one', 'two', 'three'] :  true
['one', 'two', 'three'] == ['one', 'three', 'two'] :  true
['one', 'two', 'three'] == ['one', 'two', 'three', 'three'] :  false
['one', 'two', 'three'] == ['one', 'two', 'three', 'four'] :  false
['one', 'two', 'three'] == ['one', 'two', 'four'] :  false
['one', 'two', 'three'] == ['one'] :  false

Ich hoffe, dass ich dies ohne eine Karte tun kann.

Answer 1

Python hat einen eingebauten Datentyp für eine ungeordnete Sammlung von (hashbaren) Dingen, genannt a set . Wenn Sie beide Listen in Sets umwandeln, wird der Vergleich ungeordnet sein.

set(x) == set(y)

Dokumentation über set

---

EDIT: @mdwhatcott weist darauf hin, dass man nach Duplikaten suchen sollte. set ignoriert diese, so dass Sie eine ähnliche Datenstruktur benötigen, die auch die Anzahl der Elemente in jeder Liste festhält. Dies wird als Multiset ; die beste Annäherung in der Standardbibliothek ist eine collections.Counter :

>>> import collections
>>> compare = lambda x, y: collections.Counter(x) == collections.Counter(y)
>>> 
>>> compare([1,2,3], [1,2,3,3])
False
>>> compare([1,2,3], [1,2,3])
True
>>> compare([1,2,3,3], [1,2,2,3])
False
>>>

Answer 2

Wenn die Elemente immer fast sortiert sind, wie in Ihrem Beispiel, dann wird builtin .sort() ( timsort ) sollte schnell sein:

>>> a = [1,1,2]
>>> b = [1,2,2]
>>> a.sort()
>>> b.sort()
>>> a == b
False

Wenn Sie nicht an Ort und Stelle sortieren wollen, können Sie sorted() .

In der Praxis könnte es immer schneller sein als collections.Counter() (trotz asymptotischer O(n) Zeit ist besser als O(n*log(n)) para .sort() ). Messen Sie es; wenn es wichtig ist.

Answer 3

sorted(x) == sorted(y)

Ich kopiere von hier: Prüfen, ob zwei ungeordnete Listen gleich sind

Ich denke, dies ist die beste Antwort auf diese Frage, weil

1. Dies ist besser als die Verwendung von Zählern, wie sie in diese Antwort
2. x.sort() sortiert x, was ein Nebeneffekt ist. sorted(x) gibt eine neue Liste zurück.

Answer 4

Sie wollen sehen, ob sie dieselben Elemente enthalten, aber die Reihenfolge ist Ihnen egal.

Sie können ein Set verwenden:

>>> set(['one', 'two', 'three']) == set(['two', 'one', 'three'])
True

Das Set-Objekt selbst enthält jedoch nur eine Instanz jedes einzelnen Wertes und behält die Reihenfolge nicht bei.

>>> set(['one', 'one', 'one']) == set(['one'])
True

Wenn also die Verfolgung von Duplikaten/Länge wichtig ist, sollten Sie wahrscheinlich auch die Länge überprüfen:

def are_eq(a, b):
    return set(a) == set(b) and len(a) == len(b)

Answer 5

Unter der Annahme, dass Sie bereits wissen, dass Listen gleich groß sind, garantiert die folgende Gleichung "Wahr", wenn und nur wenn zwei Vektoren genau gleich sind (einschließlich der Reihenfolge)

functools.reduce(lambda b1,b2: b1 and b2, map(lambda e1,e2: e1==e2, listA, ListB), True)

Beispiel:

>>> from functools import reduce
>>> def compvecs(a,b):
...     return reduce(lambda b1,b2: b1 and b2, map(lambda e1,e2: e1==e2, a, b), True)
... 
>>> compvecs(a=[1,2,3,4], b=[1,2,4,3])
False
>>> compvecs(a=[1,2,3,4], b=[1,2,3,4])
True
>>> compvecs(a=[1,2,3,4], b=[1,2,4,3])
False
>>> compare_vectors(a=[1,2,3,4], b=[1,2,2,4])
False
>>>