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

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

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

all(x in two for x in one)

Erläuterung: Generator erstellt Boolesche Werte durch Durchlaufen der Liste one, um zu prüfen, ob sich dieses Element in der Liste two befindet. all() gibt True zurück, wenn jedes Element wahr ist, andernfalls False. 

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

Angenommen, die Elemente sind hashierbar

>>> 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 Artikel interessieren, z. [1, 2, 2] und [1, 2] verwenden Sie dann einfach:

>>> 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?

.issubset wird der schnellste Weg sein. Das Prüfen der Länge vor dem Testen von issubset verbessert die Geschwindigkeit nicht, da Sie immer noch O (N + M) -Elemente zum Durchlaufen und Überprüfen haben. 

Ich weiß, es ist spät, wollte aber nur die Antwort mit dem aktualisieren, was für mich funktioniert hat. (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])

Prost.

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)

Die Schnittmenge der Mengen würde set one enthalten.

(ODER)

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

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

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

Zum Beispiel:

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 einen Vergleich darstellt: 1,3,5 gegenüber 1,3,4,5. Sie müssen alle Duplikate angeben.

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 das ausführen, erhalten Sie:

$ python contained.py 
b in a:  False
b in a:  True

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

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

Wenn list1 in list 2 ist:

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

• wenn wir eine set(x in two for x in one) machen, hat es nur ein Element (True).

Versuchen Sie bitweise AND

>>> set([1,2]) & set([1,2,3])
set([1, 2])
>>> set([0]) & set([1,2,3])
set([])

Hab es noch nicht erfasst.

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

Um zu überprüfen, ob eine set A Teilmenge von set B Ist, hat PythonA.issubset(B) und A <= B. Es funktioniert nur mit set 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 mir einen Algorithmus ausgedacht, um zu überprüfen, ob list A Eine Teilmenge von list B Ist.

• Um die Komplexität beim Auffinden von Teilmengen zu verringern, finde ich es angemessen, zuerst beide Listen mit sort zu vergleichen, bevor Elemente verglichen werden, um sich für Teilmengen zu qualifizieren.
• Es hat mir geholfen, break das loop zu setzen, wenn der Wert des Elements der zweiten Liste B[j] Größer ist als der Wert des Elements der ersten Liste A[i].
• last_index_j Wird verwendet, um loop über list B An der Stelle zu beginnen, an der es zuletzt aufgehört hat. Es hilft zu vermeiden, Vergleiche ab dem Start von list B Zu starten (was, wie Sie vielleicht für unnötig halten, das Starten von list B Ab index 0 In nachfolgendem iterations ist).

• Die Komplexität ist jeweils O(n ln n) zum Sortieren beider Listen und O(n) zum Überprüfen auf Teilmengen.
  O(n ln n) + O(n ln n) + O(n) = O(n ln n).

• Code enthält viele print Anweisungen, um zu sehen, was bei jedem iteration des loop vor sich geht. Diese sind nur zum Verständnis gedacht.

Überprüfen Sie, ob eine Liste Teilmenge 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

Hier ist, wie ich weiß, ob eine Liste eine Teilmenge einer anderen ist, die Reihenfolge ist für mich in meinem Fall von Bedeutung.

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

In Python 3.5 können Sie eine [*set()][index] ausführen, 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 nur mit len ​​und set

len(set(a+b)) == len(set(a))

Der folgende Code prüft, ob eine gegebene 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)