Mengen

Mengen¶

Einführung¶

Auch wenn die Mengenlehre über lange Zeit heftig kritisiert wurde und immer noch kritisiert wird, ist sie ein wesentliches Gebiet der Mathematik. Die heutige Mathematik ist in der Terminologie der Mengenlehre formuliert und baut auf deren Axiomen auf. Die Mengenlehre ist noch ein recht junges Gebiet der Mathematik. Der deutsche Mathematiker Georg Cantor (1845 - 1918) begründete die Mengenlehre mit seinem 1874 erschienenen Artikel "Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen". Anfangs also bis ins Jahr 1877 bezeichnete er übrigens noch die Mengenlehre als "Mannigfaltigkeitslehre".

1895 gab er folgende Definition einer Menge: "Unter einer 'Menge' verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objekten m unserer Anschauung oder unseres Denkens (welche die 'Elemente' von M genannt werden) zu einem Ganzen."

Eine Menge kann beliebige Elemente enthalten: zum Beispiel Zahlen, Zeichen, Buchstaben, Wörter, Namen oder sogar andere Mengen. Eine Menge wird in der Mathematik üblicherweise mit einem Großbuchstaben bezeichnet.

Mengen in Python¶

Der Datentyp "set", der ein sogenannter "collection"-Typ ist, ist in Python seit Version 2.4. enthalten. Ein set enthält eine ungeordnete Sammlung von einmaligen und unveränderlichen Elementen. In anderen Worten: Ein Element kann in einem set-Objekt nicht mehrmals vorkommen, was bei Listen und Tupel jedoch möglich ist. Beim Datentyp set handelt es sich um die Python-Implementierung von Mengen, wie sie aus der Mathematik bekannt sind.

Sets erzeugen¶

Will man eine Menge erzeugen, so ist dies in Python3 sehr einfach. Man bedient sich der gewohnten mathematischen Schreibweise.

Wenn man sich das obige Beispiel genau anschaut, fällt auf, dass print die Elemente nicht notwendigerweise in der Reihenfolge der Definition ausgibt. Python-Sets sind ungeordnete Sammlungen: Sie speichern keine Elementpositionen und garantieren keine Einfügereihenfolge. Auf eine beobachtete Iterations- oder Ausgabereihenfolge sollte man sich deshalb nicht verlassen.

Set-Elemente müssen hashbar sein. Listen und Dictionaries sind beispielsweise nicht hashbar und können deshalb keine Set-Elemente sein. „Unveränderlich“ ist als Faustregel oft hilfreich, aber technisch ist Hashbarkeit die entscheidende Eigenschaft.

Mit Tupeln funktioniert es nur dann, wenn das jeweilige Tupel selbst hashbar ist. Ein Tupel, das beispielsweise eine Liste enthält, ist ebenfalls nicht hashbar.

Neben Set-Literalen mit geschweiften Klammern gibt es den Konstruktor set(). Er akzeptiert ein beliebiges Iterable, nicht nur Sequenzen. So kann man etwa eine Liste oder einen String in eine Menge eindeutiger Elemente überführen.

Eine leere Menge schreibt man als set(). Die Schreibweise {} erzeugt dagegen ein leeres Dictionary.

Häufig wird die set-Funktion angewendet, um aus Listen oder anderen sequentiellen Datentypen mehrfache Vorkommen zu entfernen. Wir wollen dies in einem Beispiel mit einer Liste von Städten aus der Schweiz, Österreich und Deutschland zeigen. In dieser Liste erscheint die Stadt Zürich zweimal. In der erzeugten Menge erscheint sie wie erwartet nur noch einmal, da es in einer Menge keine mehrfachen Vorkommen geben kann:

Anschließend kann man dann wieder die Menge in eine Liste wandeln, falls man eine Liste als Datentyp braucht:

Wie wir sehen können, hat diese Vorgehensweise einen kleinen Schönheitsfehler. Mehrfache Vorkommen sind zwar nun nicht mehr in der Ergebnisliste enthalten, aber die ursprüngliche Reihenfolge ist in der Regel nicht mehr vorhanden.

Wir kommen nun zu einem weiteren Anwendungsfall der set-Funktion. Im folgenden Beispiel benutzen wir sie, um einen String in seine Zeichen zu vereinzeln:

Mengen aus hashbaren Elementen¶

Die Elemente eines Sets müssen hashbar sein. Deshalb sind Listen als Elemente nicht erlaubt. Hashbare Tupel, Strings, Zahlen und frozenset-Objekte sind typische Beispiele zulässiger Set-Elemente.

Frozensets¶

Ein set ist selbst veränderlich und deshalb nicht hashbar. Ein frozenset enthält ebenfalls eindeutige hashbare Elemente, kann nach seiner Erzeugung aber nicht mehr verändert werden. Dadurch ist ein frozenset selbst hashbar und kann beispielsweise als Dictionary-Schlüssel oder als Element eines anderen Sets dienen.

Frozensets besitzen die nicht-verändernden Mengenoperationen wie Vereinigung, Schnitt oder Differenz, aber keine mutierenden Methoden wie add() oder remove():

Operationen auf set-Objekten¶

add-Methode¶

Mit add() fügt man ein hashbares Objekt in ein Set ein, falls es noch nicht vorhanden ist. Ein erneutes Hinzufügen desselben Wertes verändert das Set nicht.

Selbstverständlich wird ein Objekt nur dann als neues Element eingefügt, wenn es noch nicht enthalten ist. Ist es bereits enthalten, hat der Aufruf der Methode keine Auswirkungen.

clear-Methode¶

Alle Elemente einer Menge werden entfernt. Die Menge ist also anschließend leer, wie wir im folgenden Beispiel sehen:

copy-Methode¶

copy erzeugt eine flache Kopie einer Menge, die zurückgeliefert wird. Wir demonstrieren die Benutzung anhand eines Beispiels:

Nur für diejenigen, die glauben, dass eine einfache Zuweisung auch genügen könnte:

Die Zuweisung "cities_backup = more_cities" erzeugt nur einen Pointer, einen weiteren Namen für das gleiche Objekt.

difference-Methode¶

Diese Methode liefert die Differenz von zwei oder mehr Mengen zurück. Wir illustrieren dies wie immer an einem Beispiel:

Statt die Methode "difference" zu benutzen, hätten wir auch den Operator "-" benutzen können:

difference_update-Methode¶

Die Methode "difference_update" entfernt alle Elemente einer anderen Menge aus einer Menge. "x.difference_update(y)" ist gleichbedeutend mit "x = x - y".

discard-Methode¶

Beim Aufruf von discard(el) wird das Element el aus einer Menge entfernt, falls es enthalten ist. Falls el nicht in der Menge enthalten ist, passiert nichts.

remove-Methode¶

Die Methode "remove" funktioniert wie discard(), aber falls el nicht in der Menge enthalten ist, wird ein Fehler generiert, d.h. ein KeyError:

union-Methode¶

Die Methode "union" liefert die Vereinigung von zwei Mengen als eine neue Menge zurück, d.h. alle Elemente, die in beiden Mengen vorkommen.

Um die Vereinigen zu bilden kann man auch das Pipe-Zeichen "|" als Operator verwenden:

intersection-Methode¶

Mit der Methode intersection kann man die Schnittmenge von zwei Mengen bilden, wie wir im folgenden Beispiel sehen.

Dies kann auch mit dem "&"-Zeichen formuliert werden:

isdisjoint-Methode¶

Diese Methode liefert True zurück, wenn zwei Mengen eine leere Schnittmenge haben.

issubset-Methode¶

x.issubset(y) liefert True zurück, falls x eine Untermenge von y ist. "<=" kann statt dem Aufruf der Methode verwendet werden. "<" prüft, ob es sich um eine echte Untermenge handelt: Wenn x < y gilt, dann enthält y mindestens ein Element, das nicht in x enthalten ist.

issuperset-Methode¶

x.issuperset(y) liefert True zurück, falls x eine Obermenge von y ist. ">=" kann statt dem Aufruf der Methode verwendet werden. ">" prüft, ob es sich um eine echte Obermenge handelt: Wenn x > y gilt, dann enthält x mindestens ein Element, dass nicht in y enthalten ist.

pop¶

pop() liefert ein beliebiges Element der Menge zurück. Dieses Element wird dabei aus der Menge entfernt. Die Methode erzeugt einen KeyError, falls die Menge leer ist.

Auch wenn "pop" die Elemente in der Reihenfolge der internen Repräsentierung der Menge zurückliefert, so stimmt dennoch die Formulierung "pop() liefert ein beliebiges Element der Menge zurück." Die Menge die wir im "Kopf" haben, lautet ja im obigen Beispiel {"a","b","c","d","e"} und die Reihenfolge in der pop() die Elemente zurückliefert ist 'd', 'e', 'a', 'b', 'c'. Dass diese Reihenfolge für diese Menge nicht immer gleich ist, kann man in der folgenden neuen interaktiven Python-Sitzung sehen:

Keine definierte Reihenfolge¶

Sets haben keine definierte Elementreihenfolge. Die konkrete Reihenfolge bei Iteration oder Darstellung ergibt sich aus Implementierungsdetails der Hash-Tabelle und kann sich beispielsweise durch einen anderen Programmlauf, eine andere Python-Version oder Änderungen an der Menge unterscheiden. Sie ist nicht zufällig im mathematischen Sinn, aber sie ist auch keine zugesicherte Programmschnittstelle.

Wenn eine stabile Reihenfolge benötigt wird, muss sie explizit hergestellt werden, beispielsweise mit sorted(menge) für gegenseitig vergleichbare Elemente.