Python - Überprüfen, ob eine Liste eine Untermenge der anderen ist

Die performante Funktion Python bietet für diese ist set.issubset. Es gibt ein paar Einschränkungen, die machen es unklar, ob es die Antwort auf deine Frage, aber.

Einer Liste enthalten möglicherweise Elemente mehrfach und hat einen spezifischen Auftrag. Set nicht. Eine hohe Leistung setzt die Arbeit an hashable nur Objekte.

Sind Sie gefragt Teilmenge oder Folge (das heißt, Sie brauchen eine string-Suche-Algorithmus)? Entweder die Listen werden auch für viele tests? Was sind die Datentypen in der Liste enthalten? Und für diese Angelegenheit, muss es eine Liste?

Ihren anderen Beitrag schneiden Sie ein dict und Liste gemacht, die Typen klarer und bekam eine Empfehlung zur Anwendung von Wörterbuch-Schlüssel-Ansichten für Ihre set-wie funcitonality. In diesem Fall war es bekannt, um zu arbeiten, weil Wörterbuch-Tasten Verhalten sich wie eine Reihe (so viel, so dass wir je hatten-sets in Python, die wir verwendet, Wörterbücher). Man fragt sich, wie sich das Problem hab weniger spezifisch in drei Stunden.

InformationsquelleAutor der Antwort Yann Vernier

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

all(x in two for x in one)

Erklärung: Generator erstellen Boolesche Werte, indem die Schleife durch die Liste one überprüfung, ob das Element in der Liste two. all() zurück True wenn jedes Element ist truthy, sonst False.

Es ist auch ein Vorteil, dass all False zurück auf die erste Instanz von einem element fehlt, anstatt Sie zu verarbeiten jeden Artikel.

InformationsquelleAutor der Antwort voidnologo

Ich weiß, das ist spät, aber wollte nur aktualisieren Sie die Antwort mit dem, was für mich gearbeitet
(Python 3)

# var 1
x = [1,2,3,4]
#  var 2
y = [1,2]

# check if var2 is subset of var1
all([z in x for z in y])

Cheers.

InformationsquelleAutor der Antwort Mohit

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

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

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

Den Schnittpunkt der Sätze enthalten würde, der set one

(ODER)

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

set(one) & (set(two)) == set(one)

InformationsquelleAutor der Antwort Vikram S

Mir verzeihen, wenn ich zu spät zu der party. 😉

Um zu überprüfen, ob eine set A ist Teilmenge von set BPython hat A.issubset(B) und A <= B. Es funktioniert auf set nur und funktioniert Super ABER die Komplexität der internen Umsetzung ist unbekannt. Referenz: https://docs.python.org/2/library/sets.html#set-objects

Kam ich mit einen Algorithmus, um zu überprüfen, ob list A ist eine Teilmenge von list B mit folgenden Bemerkungen.

• Zu reduzieren, Komplexität zu finden, Teilmenge, finde ich es angemessen
  sort beiden Listen den ersten, bevor vergleichen von Elementen zu qualifizieren
  Teilmenge.
• Es hat mir geholfen break die loop wenn der Wert des element der zweiten Liste B[j] größer ist als der Wert des element der ersten Liste A[i].
• last_index_j zu starten loop über list B wo Sie zuletzt aufgehört haben. Es hilft zu vermeiden, ab-Vergleiche vom Beginn der
  list B (das ist, wie Sie vielleicht erraten, unnötig, zu starten list B aus index 0 im nachfolgenden iterations.)

• Komplexität O(n ln n) jeweils für die Sortierung der beiden Listen und O(n) für die Prüfung für die Teilmenge.
  
  O(n ln n) + O(n ln n) + O(n) = O(n ln n).

• Code hat viele print Anweisungen, um zu sehen, was Los ist bei jeder iteration des loop. Diese sollen die für das Verständnis
  nur.

Prüfen Sie, ob eine Liste ist Teilmenge der anderen Liste

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

InformationsquelleAutor der Antwort Hamza Rashid

Folgende code prüft, ob ein gegebener Satz ist eine "echte Teilmenge" einer anderen Gruppe

 def is_proper_subset(set, superset):
     return all(x in superset for x in set) and len(set)<len(superset)

InformationsquelleAutor der Antwort Leo Bastin

Wenn Sie gefragt werden, ob eine Liste "enthalten" in einer anderen Liste dann:

>>>if listA in listB: return True

Wenn Sie gefragt werden, ob jedes element in listA hat die gleiche Anzahl der übereinstimmenden Elemente in listB versuchen:

all(True if listA.count(item) <= listB.count(item) else False for item in listA)

InformationsquelleAutor der Antwort DevPlayer