Wie kann ich überprüfen, ob eine Liste eine Teilmenge einer anderen ist?

184

Ich muss überprüfen, ob eine Liste eine Teilmenge einer anderen ist - eine boolesche Rückgabe ist alles, was ich suche.

Ist das Testen der Gleichheit auf der kleineren Liste nach einer Kreuzung der schnellste Weg, dies zu tun? Die Leistung ist angesichts der Anzahl der zu vergleichenden Datensätze von größter Bedeutung.

Hinzufügen weiterer Fakten basierend auf Diskussionen:

  1. Wird eine der Listen für viele Tests gleich sein? Es handelt sich um eine statische Nachschlagetabelle.

  2. Muss es eine Liste sein? Dies ist nicht der Fall - die statische Nachschlagetabelle kann alles sein, was am besten funktioniert. Das dynamische ist ein Diktat, aus dem wir die Schlüssel extrahieren, um eine statische Suche durchzuführen.

Was wäre angesichts des Szenarios die optimale Lösung?

Unbekannt
quelle
Sie erwähnen Geschwindigkeit, vielleicht wäre Numpy nützlich, abhängig von Ihrer Verwendung.
NinMonkey
2
Sind die Listenelemente hashbar?
wim
2
Wenn die Reihenfolge wichtig ist, ist dies möglicherweise ein guter Anfang - StackOverflow - Bester Weg, um
Benötigen Sie eine geeignete Teilmenge oder können sie gleich sein?
Törzsmókus
2
Warum nicht set (list_a) .issubset (set (list_b))?
SeF

Antworten:

126

Die performante Funktion, die Python dafür bereitstellt, ist set.issubset. Es gibt jedoch einige Einschränkungen, die unklar machen, ob dies die Antwort auf Ihre Frage ist.

Eine Liste kann Elemente mehrmals enthalten und hat eine bestimmte Reihenfolge. Ein Set nicht. Außerdem funktionieren Sets nur für hashbare Objekte.

Fragen Sie nach Teilmengen oder Teilsequenzen (was bedeutet, dass Sie einen String-Suchalgorithmus wünschen)? Wird eine der Listen für viele Tests gleich sein? Welche Datentypen sind in der Liste enthalten? Und muss es eine Liste sein?

Ihr anderer Beitrag schneidet ein Diktat und eine Liste , um die Typen klarer zu machen, und erhielt die Empfehlung, Wörterbuchschlüsselansichten für ihre satzähnliche Funktionalität zu verwenden. In diesem Fall war bekannt, dass es funktioniert, weil sich Wörterbuchschlüssel wie eine Menge verhalten (so sehr, dass wir Wörterbücher verwendeten, bevor wir Mengen in Python hatten). Man fragt sich, wie das Problem in drei Stunden weniger spezifisch wurde.

Yann Vernier
quelle
Ich beziehe mich nur auf eine Teilmenge und issubset funktioniert einwandfrei - Danke. Ich bin jedoch neugierig auf 2 Fragen hier. 1.Wird eine der Listen für viele Tests gleich sein? Es handelt sich um eine statische Nachschlagetabelle. 2. Muss es sich um eine Liste handeln? Dies ist nicht der Fall - die statische Nachschlagetabelle kann alles sein, was am besten funktioniert. Das dynamische ist ein Diktat, aus dem wir die Schlüssel extrahieren, um eine statische Suche durchzuführen. Wird diese Tatsache die Lösung verändern?
Unbekannt
Nicht viel. Die Schlüssel eines Wörterbuchs sind satzartig und bereits in einer Hash-Tabelle angeordnet. Daher führt die Verwendung eines Satzes für den statischen Teil nicht zu zusätzlichen Komplikationen. Grundsätzlich bedeutet die Tatsache, dass es sich um ein Diktat handelt, dass Sie den statischen Teil möglicherweise nicht in eine Menge konvertieren müssen (Sie können alle (itertools.imap (dict.has_key, mylist)) mit O (n) -Leistung überprüfen).
Yann Vernier
Ich verstehe nicht, wie diese (oder jede andere Lösung, die auf Sets basiert) hier die akzeptierte Antwort sein kann. Die Frage bezieht sich auf Listen, und ich denke ehrlich gesagt, dass die Teilmenge in "Überprüfen, ob eine Liste eine Teilmenge der anderen ist" nicht wörtlich zu verstehen ist. Bei der Konvertierung in Mengen gehen alle Informationen zu doppelten Elementen verloren. Wenn die ursprüngliche Liste diese jedoch enthalten könnte, ist es möglicherweise wichtig zu überprüfen, ob sie auch in der zweiten Liste enthalten sind, um wirklich zu sagen, dass alle Elemente einer Liste gefunden werden können innerhalb des anderen. Sets machen das nicht!
InVader
Kontext ist wichtig; Dies wurde akzeptiert, um dem Fragesteller zu helfen, und erklärte die Unterscheidung. Uns wurde gesagt, dass die Kandidaten als Sets darstellbar sein würden, also war es eine Set-Aufgabe. Ihr Fall könnte anders sein, und der von Ihnen erwähnte Unterschied würde mithilfe von Multisets wie Sammlungen gelöst.
Yann Vernier
140
>>> a = [1, 3, 5]
>>> b = [1, 3, 5, 8]
>>> c = [3, 5, 9]
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

>>> a = ['yes', 'no', 'hmm']
>>> b = ['yes', 'no', 'hmm', 'well']
>>> c = ['sorry', 'no', 'hmm']
>>> 
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False
Yulan Liu
quelle
21
Das sieht am schönsten aus und schreibt am einfachsten, aber das schnellste sollte sein, set(a).issubset(b) weil Sie in diesem Fall nur ain set konvertieren , aber nicht b, was Zeit spart. Sie können timeitdie in zwei Befehlen verbrauchte Zeit vergleichen. Zum Beispiel timeit.repeat('set(a)<set(b)', 'a = [1,3,5]; b = [1,3,5,7]', number=1000) und timeit.repeat('set(a).issubset(b)', 'a = [1,3,5]; b = [1,3,5,7]', number=1000)
Yulan Liu
8
@YulanLiu: Ich hasse es, es Ihnen zu brechen, aber das allererste, wasissubsetsetfrozensetsetset Sie tun müssen, ist zu überprüfen, ob das Argument ein / ist , und wenn dies nicht der Fall ist , konvertiert es es zum Vergleich in ein temporäres Argument , führt die Überprüfung aus und wirft das temporäre dann weg . Zeitliche Unterschiede (falls vorhanden) sind ein Faktor für kleine Unterschiede bei den LEGB-Suchkosten ( setein zweites Mal zu finden ist teurer als die Attributsuche bei einem vorhandenen set), aber es ist meistens eine Wäsche für ausreichend große Eingaben.
ShadowRanger
3
Wenn beide Listen dieselben Werte enthalten, wird dieser Wert false zurückgeben. Stattdessen sollte die Bedingung gesetzt werden (a) <= set (b)
ssi-anik
2
Wie kann diese Antwort richtig sein? Er bat um eine Liste, nicht um einen Satz. Sie sind völlig anders. Was ist, wenn a = [1, 3, 3, 5, 5] und b = [1, 3, 3, 3, 5]. Die Mengenlehre ist für Duplikate ungeeignet.
Eamonn Kenny
1
Ich möchte auch darauf hinweisen, dass wenn a = [1,3,5] und b = [1,3,5], set (a) <set (b) False zurückgibt. Sie können den Operator equals hinzufügen, um diese Fälle zu behandeln: dh set (a) <= set (b).
Jon
37
one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

all(x in two for x in one)

Erläuterung: Der Generator erstellt Boolesche Werte, indem er die Liste durchläuft und oneprüft, ob sich dieses Element in der Liste befindet two. Gibt all()zurück, Truewenn jeder Artikel wahr ist False.

Es gibt auch den Vorteil, dass allFalse bei der ersten Instanz eines fehlenden Elements zurückgegeben wird, anstatt jedes Element verarbeiten zu müssen.

voidnologo
quelle
Ich denke, für die Lesbarkeit und die explizite Darstellung dessen, was Sie erreichen möchten, set(one).issubset(set(two))ist dies eine großartige Lösung. Mit der von mir veröffentlichten Lösung sollten Sie sie mit allen Objekten verwenden können, wenn für sie die richtigen Vergleichsoperatoren definiert sind.
voidnologo
4
Verwenden Sie einen Generatorausdruck, kein Listenverständnis. Ersteres ermöglicht alleinen ordnungsgemäßen Kurzschluss, letzteres führt alle Überprüfungen durch, auch wenn aus der ersten Überprüfung hervorgeht, dass der Test fehlschlagen würde. Lassen Sie einfach die eckigen Klammern fallen, um zu erhalten all(x in two for x in one).
ShadowRanger
Liege ich falsch oder kannst du diese Methode nicht bei Einheimischen anwenden?
Homper
22

Angenommen, die Elemente sind hashbar

>>> from collections import Counter
>>> not Counter([1, 2]) - Counter([1])
False
>>> not Counter([1, 2]) - Counter([1, 2])
True
>>> not Counter([1, 2, 2]) - Counter([1, 2])
False

Wenn Sie sich nicht für doppelte Elemente interessieren, z. [1, 2, 2]und [1, 2]dann einfach benutzen:

>>> set([1, 2, 2]).issubset([1, 2])
True

Ist das Testen der Gleichheit auf der kleineren Liste nach einer Kreuzung der schnellste Weg, dies zu tun?

.issubsetwird der schnellste Weg sein, dies zu tun. Das Überprüfen der Länge vor dem Testen issubsetverbessert die Geschwindigkeit nicht, da Sie noch O (N + M) -Elemente durchlaufen und überprüfen müssen.

Jamylak
quelle
6

Eine weitere Lösung wäre die Verwendung von a intersection.

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one).intersection(set(two)) == set(one)

Der Schnittpunkt der Mengen würde von enthalten set one

(ODER)

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one) & (set(two)) == set(one)
SuperNova
quelle
2
one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(x in two for x in one) == set([True])

Wenn Liste1 in Liste 2 enthalten ist:

  • (x in two for x in one)generiert eine Liste von True.

  • Wenn wir dies tun, set(x in two for x in one)hat a nur ein Element (True).

SuperNova
quelle
2

Die Mengenlehre ist für Listen ungeeignet, da Duplikate mit der Mengenlehre zu falschen Antworten führen.

Beispielsweise:

a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
set(b) > set(a)

Hat keine Bedeutung. Ja, es gibt eine falsche Antwort, aber dies ist nicht korrekt, da die Mengenlehre nur vergleicht: 1,3,5 gegenüber 1,3,4,5. Sie müssen alle Duplikate einschließen.

Stattdessen müssen Sie jedes Vorkommen jedes Elements zählen und eine Prüfung durchführen, die größer als gleich ist. Dies ist nicht sehr teuer, da keine O (N ^ 2) -Operationen verwendet werden und keine schnelle Sortierung erforderlich ist.

#!/usr/bin/env python

from collections import Counter

def containedInFirst(a, b):
  a_count = Counter(a)
  b_count = Counter(b)
  for key in b_count:
    if a_count.has_key(key) == False:
      return False
    if b_count[key] > a_count[key]:
      return False
  return True


a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

a = [1, 3, 3, 3, 4, 4, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

Wenn Sie dies ausführen, erhalten Sie:

$ python contained.py 
b in a:  False
b in a:  True
Eamonn Kenny
quelle
0

Verzeihen Sie mir, wenn ich zu spät zur Party komme. ;)

Um zu überprüfen, ob eine set ATeilmenge von ist set B, Pythonhat A.issubset(B)und A <= B. Es funktioniert setnur und funktioniert hervorragend, ABER die Komplexität der internen Implementierung ist unbekannt. Referenz: https://docs.python.org/2/library/sets.html#set-objects

Ich habe einen Algorithmus entwickelt, um zu überprüfen, ob list Aes sich um eine Teilmenge der list Bfolgenden Anmerkungen handelt.

  • Um die Komplexität beim Finden von Teilmengen zu verringern, halte ich es zunächst für angemessen, sortbeide Listen zu vergleichen, bevor Elemente verglichen werden, um sich für Teilmengen zu qualifizieren.
  • Es hat mir geholfen, breakdas , loopwenn der Wert des Elements der zweiten Liste B[j]ist größer als der Wert des Elements der ersten Liste A[i].
  • last_index_jwird verwendet , um Start loopüber , list Bwo er aus dem letzten links. Es hilft vermeiden Vergleiche ausgehend vom Beginn list B(das ist, wie Sie unnötige vorstellen können, starten list Baus index 0in der Folge iterations.)
  • Die Komplexität besteht O(n ln n)jeweils darin, beide Listen zu sortieren und O(n)nach Teilmengen zu suchen.
    O(n ln n) + O(n ln n) + O(n) = O(n ln n).

  • Code hat viele printAnweisungen, um zu sehen, was bei jedem iterationder beiden los ist loop. Diese sind nur zum Verständnis gedacht.

Überprüfen Sie, ob eine Liste Teil einer anderen Liste ist

is_subset = True;

A = [9, 3, 11, 1, 7, 2];
B = [11, 4, 6, 2, 15, 1, 9, 8, 5, 3];

print(A, B);

# skip checking if list A has elements more than list B
if len(A) > len(B):
    is_subset = False;
else:
    # complexity of sorting using quicksort or merge sort: O(n ln n)
    # use best sorting algorithm available to minimize complexity
    A.sort();
    B.sort();

    print(A, B);

    # complexity: O(n^2)
    # for a in A:
    #   if a not in B:
    #       is_subset = False;
    #       break;

    # complexity: O(n)
    is_found = False;
    last_index_j = 0;

    for i in range(len(A)):
        for j in range(last_index_j, len(B)):
            is_found = False;

            print("i=" + str(i) + ", j=" + str(j) + ", " + str(A[i]) + "==" + str(B[j]) + "?");

            if B[j] <= A[i]:
                if A[i] == B[j]:
                    is_found = True;
                last_index_j = j;
            else:
                is_found = False;
                break;

            if is_found:
                print("Found: " + str(A[i]));
                last_index_j = last_index_j + 1;
                break;
            else:
                print("Not found: " + str(A[i]));

        if is_found == False:
            is_subset = False;
            break;

print("subset") if is_subset else print("not subset");

Ausgabe

[9, 3, 11, 1, 7, 2] [11, 4, 6, 2, 15, 1, 9, 8, 5, 3]
[1, 2, 3, 7, 9, 11] [1, 2, 3, 4, 5, 6, 8, 9, 11, 15]
i=0, j=0, 1==1?
Found: 1
i=1, j=1, 2==1?
Not found: 2
i=1, j=2, 2==2?
Found: 2
i=2, j=3, 3==3?
Found: 3
i=3, j=4, 7==4?
Not found: 7
i=3, j=5, 7==5?
Not found: 7
i=3, j=6, 7==6?
Not found: 7
i=3, j=7, 7==8?
not subset
Hamza Rashid
quelle
Wenn Sie sie sortieren, gibt es keinen Grund mehr, eine Liste anstelle eines Satzes zu verwenden…
LtWorf
0

Der folgende Code prüft, ob eine bestimmte Menge eine "richtige Teilmenge" einer anderen Menge ist

 def is_proper_subset(set, superset):
     return all(x in superset for x in set) and len(set)<len(superset)
Leo Bastin
quelle
1
Warum ist Ihr Ideal für die leere Menge, um die etablierte mathematische Regel zu brechen? Wikipedia: Die mit ∅ bezeichnete leere Menge {} ist auch eine Teilmenge einer bestimmten Menge X. Sie ist auch immer eine richtige Teilmenge einer Menge außer sich selbst.
Yann Vernier
Danke @YannVernier Ich habe geändert, dass leere Prüfungen sowohl für die Teilmenge als auch für die Obermenge eingeschlossen sind, sodass false zurückgegeben wird, wenn beide leer sind.
Leo Bastin
Aber warum machst du das? Wenn A eine Teilmenge von B ist, bedeutet dies einfach, dass A keine Elemente enthält, die nicht in B enthalten sind, oder dass alle Elemente in A ebenfalls in B enthalten sind. Die leere Menge ist daher eine Teilmenge aller Mengen, einschließlich sich selbst. Ihre zusätzlichen Überprüfungen bestätigen, dass dies nicht der Fall ist, und Sie behaupten, dass dies irgendwie ideal ist, aber es widerspricht der etablierten Terminologie. Was ist der Vorteil?
Yann Vernier
Danke @YannVernier Jetzt prüft der Code, ob eine bestimmte Menge eine "richtige Teilmenge" einer anderen Menge ist.
Leo Bastin
Dies ist genauso schlecht wie die Antworten, die auf der Verwendung von Sets beruhen . Während eine Menge mathematisch gesehen eine Sammlung unterschiedlicher Elemente ist, können und sollten wir uns bei der Überprüfung, ob eine Liste Teil einer anderen ist, nicht auf diese Annahme verlassen. Wenn die ursprüngliche Liste ein Duplikat enthalten würde, könnte Ihre Funktion immer noch True zurückgeben , selbst wenn das betreffende Element nur einmal in der zweiten Liste vorhanden ist. Ich denke nicht, dass dies das richtige Verhalten ist, wenn versucht wird, Listen zu vergleichen.
InVader
0

In Python 3.5 können Sie a ausführen [*set()][index], um das Element abzurufen. Es ist eine viel langsamere Lösung als andere Methoden.

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

result = set(x in two for x in one)

[*result][0] == True

oder einfach mit len ​​und set

len(set(a+b)) == len(set(a))
SuperNova
quelle
0

Hier ist, woher ich weiß, ob eine Liste eine Teilmenge einer anderen ist, die Reihenfolge ist mir in meinem Fall wichtig.

def is_subset(list_long,list_short):
    short_length = len(list_short)
    subset_list = []
    for i in range(len(list_long)-short_length+1):
        subset_list.append(list_long[i:i+short_length])
    if list_short in subset_list:
        return True
    else: return False
Mindee
quelle
0

Die meisten Lösungen berücksichtigen, dass die Listen keine Duplikate enthalten. Falls Ihre Listen Duplikate enthalten, können Sie Folgendes versuchen:

def isSubList(subList,mlist):
    uniqueElements=set(subList)
    for e in uniqueElements:
        if subList.count(e) > mlist.count(e):
            return False     
    # It is sublist
    return True

Es stellt sicher, dass die Unterliste niemals andere Elemente als die Liste oder eine größere Menge eines gemeinsamen Elements enthält.

lst=[1,2,2,3,4]
sl1=[2,2,3]
sl2=[2,2,2]
sl3=[2,5]

print(isSubList(sl1,lst)) # True
print(isSubList(sl2,lst)) # False
print(isSubList(sl3,lst)) # False
Ignacio Alorre
quelle
0

Da niemand über einen Vergleich mit Zeichenfolgen nachgedacht hat, ist hier mein Vorschlag.

Sie können natürlich überprüfen, ob die Pipe ("|") nicht Teil einer der beiden Listen ist, und möglicherweise automatisch ein anderes Zeichen auswählen, aber Sie haben die Idee.

Die Verwendung einer leeren Zeichenfolge als Trennzeichen ist keine Lösung, da die Zahlen mehrere Ziffern haben können ([12,3]! = [1,23]).

def issublist(l1,l2):
    return '|'.join([str(i) for i in l1]) in '|'.join([str(i) for i in l2])
y4cine
quelle
-1

Wenn Sie fragen, ob eine Liste in einer anderen Liste "enthalten" ist, dann:

>>>if listA in listB: return True

Wenn Sie fragen, ob jedes Element in Liste A die gleiche Anzahl übereinstimmender Elemente in Liste B enthält, versuchen Sie Folgendes:

all(True if listA.count(item) <= listB.count(item) else False for item in listA)
DevPlayer
quelle
Das funktioniert bei mir nicht. Gibt false zurück, auch wenn listA == listB
cass
@cass Ich habe nur mit Strings getestet. Versuchen Sie dies auf Ihrem Computer. pastebin.com/9whnDYq4
DevPlayer
Ich bezog mich auf den Teil "if listA in listB: return True", nicht auf den zweiten Teil.
Cass
@cass Bedenken Sie: ['eins', 'zwei'] in ['eins', 'zwei'] ergibt Falsch. ['eins', 'zwei'] in ['eins', 'zwei', 'drei'] ergibt Falsch. ['eins', 'zwei'] in [['eins', 'zwei'], 'drei'] ergibt True. Also ja, wenn listA == ListB, dann gibt listA in listB immer False zurück, da listA ein Listenelement in listB sein müsste. Vielleicht denken Sie: ListeA in ListeB bedeutet "Sind Elemente in ListeA als Elemente in ListeB aufgeführt. Dies ist nicht die Bedeutung von ListeA in ListeB
DevPlayer
@cass Ah, ich sehe, wie mein Beitrag verwirrt. Der ursprüngliche Beitrag wurde gebeten, zu testen, ob listA eine Teilmenge von listB ist. Technisch gesehen ist mein Beitrag aufgrund der Frage des ursprünglichen Beitrags falsch. Damit es richtig ist, müsste die Frage nach "if listA in [item0, item2, listA, item3, listA,]" gestellt worden sein. Nicht "Elemente in ['a', 'b', 'c'] in ['d', 'c', 'f', 'a', 'b', 'a']".
DevPlayer
-2

Wenn ja a2 is subset of a1, dannLength of set(a1 + a2) == Length of set(a1)

a1 = [1, 2, 3, 4, 5]
a2 = [1, 2, 3]

len(set(a1)) == len(set(a1 + a2))
SuperNova
quelle