Mengen



Einführung

Grafische Notation von Mengen in 
Kreisdiagrammen 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.
>>> staedte = {'Hamburg', 'München', 'Frankfurt', 'Berlin'}
>>> print(staedte)
{'München', 'Berlin', 'Frankfurt', 'Hamburg'}
>>> 'Berlin' in staedte
True
>>> 'Köln' in staedte
False
Wenn man sich das obige Beispiel einer Menge genau anschaut, dann wundert man sich sicherlich, dass die Reihenfolge der Städte durch print anders ausgegeben wird, als man die Städte bei der Definition der Menge angegeben hat. Das liegt daran, dass Mengen allgemein und auch bei der Programmiersprache Python eine ungeordnete Sammlung von verschiedenen Objekten enthalten. Es gibt also keine Reihenfolge bei Mengen, und deshalb kann die Ausgabe durch print beliebig sein. Mehr dazu finden Sie im letzten Abschnitt dieses Kapitels.
Die Elemente dürfen in Python aber nur unveränderliche Typen sein, d.h. sie dürfen beispielsweise keine Listen sein. Wir demonstrieren dies im folgenden Beispiel, in dem wir versuchen eine Menge anzulegen, die Zweierlisten mit Städten und deren Einwohnerzahlen (Stand 2013) enthalten soll:
>>> staedte = { ['Berlin', 3.42], ['Hamburg', 1.75],  ['München', 1.41], ['Köln', 1.03], ['Frankfurt', 0.70], ['Stuttgart', 0.60]}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
Nimmt man Tupel (unveränderlich) statt Listen (veränderlich) als Elemente, dann funktioniert es:
>>> staedte = {('Frankfurt', 0.7), ('Stuttgart', 0.6), ('Hamburg', 1.75), ('Berlin', 3.42), ('Köln', 1.03), ('München', 1.41)}


Noch eine Anmerkung: Diejenigen, die Dictionaries schon kennen oder bereits unser Kapitel über Dictionaries durchgearbeitet haben, mögen sich vielleicht wundern, dass wir die geschweiften Klammern auch für Mengen verwenden.

Neben dem Datentyp "set" gibt es auch eine Funktion "set()". Mit der Funktion set() kann man sequentielle Datentypen, also zum Beispiel Listen, in Mengen wandeln. Im folgenden kleinen Beispiel definieren wir eine Liste von Wörtern, die wir mittels der set()-Funktion in eine Menge wandeln:
>>> liste_von_woertern = ["gut", "hilfreich", "besser", "optimal"] 
>>> menge_von_woertern = set(liste_von_woertern) 
>>> menge_von_woertern
{'hilfreich', 'besser', 'optimal', 'gut'}
>>> 

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:

>>> liste_von_staedten = ["Frankfurt", "Zürich", "Bern", "Stuttgart", "Freiburg", "Ulm", "Hamburg", "München", "Nürnberg", "Zürich", "Bregenz", "Salzburg", "Wien"]
>>> liste_von_staedten
['Frankfurt', 'Zürich', 'Bern', 'Stuttgart', 'Freiburg', 'Ulm', 'Hamburg', 'München', 'Nürnberg', 'Zürich', 'Bregenz', 'Salzburg', 'Wien']
>>> menge_von_staedten = set(liste_von_staedten)
>>> menge_von_staedten
{'Wien', 'Bern', 'Hamburg', 'Nürnberg', 'Frankfurt', 'Bregenz', 'Zürich', 'München', 'Ulm', 'Stuttgart', 'Freiburg', 'Salzburg'}
>>> 

Anschließend kann man dann wieder die Menge in eine Liste wandeln, falls man eine Liste als Datentyp braucht:
>>> liste_von_staedten = list(menge_von_staedten)
>>> liste_von_staedten
['Wien', 'Bern', 'Hamburg', 'Nürnberg', 'Frankfurt', 'Bregenz', 'Zürich', 'München', 'Ulm', 'Stuttgart', 'Freiburg', 'Salzburg']
>>> 
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:
>>> x = set("Ein gutes Python-Tutorial")
>>> x
{'t', 'y', 'h', 'o', 's', 'P', 'a', 'l', 'e', 'E', 'r', 'n', '-', 'i', 'g', 'u', 'T', ' '}
>>> type(x)
<class 'set'>
>>> 


Mengen von unveränderlichen Elementen

Sets sind so implementiert, dass sie keine veränderlichen (mutable) Objekte erlauben. Das folgende Beispiel demonstriert, dass wir beispielsweise keine Listen als Elemente haben können:
>>> cities = set((("Python","Perl"), ("Paris", "Berlin", "London")))
>>> cities = set((["Python","Perl"], ["Paris", "Berlin", "London"]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'


Frozensets

Auch wenn sets keine veränderlichen Elemente enthalten können, sind sie selbst veränderlich. Wir können zum Beispiel neue Elemente einfügen:
>>> cities = {"Frankfurt", "Basel","Freiburg"}
>>> cities.add("Strasbourg")
>>> cities
{'Freiburg', 'Frankfurt', 'Basel', 'Strasbourg'}

Frozensets sind wie sets, aber sie können nicht verändert werden. Sie sind also unveränderlich (immutable):
>>> cities = frozenset(["Frankfurt", "Basel","Freiburg"])
>>> cities.add("Strasbourg")
Traceback (most recent call last):
  File "<stdin&module>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'
>>> 


Operationen auf "set"-Objekten


add(element)

Mit der Methode add fügt man ein Objekt in eine Menge als neues Element ein, falls es noch nicht vorhanden ist. Es gilt zu beachten, dass es sich dabei um ein unveränderliches Element handelt.
Im folgenden Beispiel fügen wir einen String ein:
>>> colours = {"red","green"}
>>> colours.add("yellow")
>>> colours
{'green', 'yellow', 'red'}
>>> colours.add(["black","white"])
Traceback (most recent call last):
  File "<stdin&module>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> 
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()

Alle Elemente einer Menge werden entfernt. Die Menge ist also anschließend leer, wie wir im folgenden Beispiel sehen:
>>> cities = {"Stuttgart", "Konstanz", "Freiburg"}
>>> cities.clear()
>>> cities
set()
>>> 

copy

copy erzeugt eine flache Kopie einer Menge, die zurückgeliefert wird. Wir demonstrieren die Benutzung anhand eines Beispiels:
>>> more_cities = {"Winterthur","Schaffhausen","St. Gallen"}
>>> cities_backup = more_cities.copy()
>>> more_cities.clear()
>>> cities_backup
{'St. Gallen', 'Winterthur', 'Schaffhausen'}
>>> 

Nur für diejenigen, die glauben, dass eine einfache Zuweisung auch genügen könnte:
>>> more_cities = {"Winterthur", "Schaffhausen", "St. Gallen"}
>>> cities_backup = more_cities
>>> more_cities.clear()
>>> cities_backup
set()
>>> 
	
Die Zuweisung "cities_backup = more_cities" erzeugt nur einen Pointer, d.h. einen weiteren Namen für das gleiche Objekt.

difference()

Diese Methode liefert die Differenz von zwei oder mehr Mengen zurück. Wir illustrieren dies wie immer an einem Beispiel:
>>> x = {"a","b","c","d","e"}
>>> y = {"b","c"}
>>> z = {"c","d"}
>>> x.difference(y)
{'e', 'd', 'a'}
>>> x.difference(y).difference(z)
{'e', 'a'}
>>> 
Statt die Methode "difference" zu benutzen, hätten wir auch den Operator "-" benutzen können:
>>> x - y
{'e', 'd', 'a'}
>>> x - y - z
{'e', 'a'}
>>> 	
	

difference_update()

Die Methode "difference_update" entfernt alle Elemente einer anderen Menge aus einer Menge. "x.difference_update()" ist gleichbedeutend mit "x = x - y"
>>> x = {"a","b","c","d","e"}
>>> y = {"b","c"}
>>> x.difference_update(y)
>>> 
>>> x = {"a","b","c","d","e"}
>>> y = {"b","c"}
>>> x = x - y
>>> x
{'e', 'd', 'a'}
>>> 
	

discard(el)

Das Element el wird aus einer Menge entfernt, falls es enthalten ist. Falls el nicht in der Menge enthalten ist, passiert nichts.
>>> x = {"a","b","c","d","e"}
>>> x.discard("a")
>>> x
{'e', 'c', 'b', 'd'}
>>> x.discard("z")
>>> x
{'e', 'c', 'b', 'd'}
>>>
	

remove(el)

Die Methode "remove" funktioniert wie discard(), aber falls el nicht in der Menge enthalten ist, wird ein Fehler generiert, d.h. ein KeyError:
>>> x = {"a","b","c","d","e"}
>>> x.remove("a")
>>> x
{'e', 'c', 'b', 'd'}
>>> x.remove("z")
Traceback (most recent call last):
  File "<stdin&module>", line 1, in <module>
KeyError: 'z'
>>> 	
	

union(s)

Die Methode "union" liefert die Vereinigung von zweo Mengen als eine neue Menge zurück, d.h. alle Elemente, die in beiden Mengen vorkommen.
>>> x = {"a","b","c","d","e"}
>>> y = {"c","d","e","f","g"}
>>> x.union(y)
{'d', 'a', 'g', 'c', 'f', 'b', 'e'}
Um die Vereinigen zu bilden kann man auch das Pipe-Zeichen "|" als Operator verwenden:
>>> x = {"a","b","c","d","e"}
>>> y = {"c","d","e","f","g"}
>>> x | y
{'d', 'a', 'g', 'c', 'f', 'b', 'e'}
>>>

intersection(s)

Liefert die Schnittmenge von s und der Instanzmenge zurück.
>>> x = {"a","b","c","d","e"}
>>> y = {"c","d","e","f","g"}
>>> x.intersection(y)
{'e', 'c', 'd'}
Dies kann auch mit dem "&"-Zeichen formuliert werden:
>>> x = {"a","b","c","d","e"}
>>> y = {"c","d","e","f","g"}
>>> x & y
{'e', 'c', 'd'}
>>> 

isdisjoint()

Diese Methode liefert True zurück, wenn zwei Mengen eine leere Schnittmenge haben.
>>> x = {"a","b","c"}
>>> y = {"c","d","e"}
>>> x.isdisjoint(y)
False
>>> 
>>> x = {"a","b","c"}
>>> y = {"d","e","f"}
>>> x.isdisjoint(y)
True
>>> 

issubset()

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.
>>> x = {"a","b","c","d","e"}
>>> y = {"c","d"}
>>> x.issubset(y)
False
>>> y.issubset(x)
True
>>> x < y
False
>>> y < x # y ist eine echte Untermenge von x
True
>>> x < x # eine Menge kann nie eine echte Untermenge ihrer selbst sein.
False
>>> x <= x
True
>>> 
	

issuperset()

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.
>>> x = {"a","b","c","d","e"}
>>> y = {"c","d"}
>>> x.issuperset(y)
True
>>> x > y
True
>>> x >= y
True
>>> x >= x
True
>>> x > x
False
>>> x.issuperset(x)
True
>>> 

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.
>>> x = {"a","b","c","d","e"}
>>> x
{'e', 'c', 'b', 'd', 'a'}
>>> x.pop()
'e'
>>> x.pop()
'c'
>>> x.pop()
'b'
>>> x.pop()
'd'
>>> x.pop()
'a'
>>> 
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 'e', 'c', 'b', 'd', 'a'.
Dass diese Reihenfolge für diese Menge nicht immer gleich ist, kann man in der folgenden neuen interaktiven Python-Sitzung sehen:
>>> x = {"a", "b", "c", "d", "e"}
>>> x.pop()
'a'
>>> x.pop()
'b'
>>> x.pop()
'e'
>>> x.pop()
'd'
>>> x.pop()
'c'
>>> 


Beliebige oder zufällige Reihenfolge

Wir haben gelernt, dass es bei Mengen keine festgelegte Reihenfolge für die Elemente gibt und dass man auch keine solche Reihenfolge definieren kann. Wie wir anfangs gesagt haben ist die Reihenfolge bei Mengen beliebig. "Beliebig" darf man aber nicht mit "zufällig" verwechseln. Prinzipiell könnte es beispielsweise sein, dass Python die Elemente einer bestimmten Menge immer in der gleichen Reihenfolge intern abspeichert, was man dann bei der Ausgabe der Menge sehen kann. Dies ist aber nicht so. Die Reihenfolge hängt ab von einem Hash, einer speziellen Funktion, die bei Dictionaries und Mengen verwendet wird. Bei verschiedenen Programmläufen kann dies dann zu unterschiedlichen Repräsentationen der Menge führen. Wir demonstrieren dies im folgenden Beispiel:
bernd@saturn:~$ python3
Python 3.4.0 (default, Apr 11 2014, 13:05:11) 
[GCC 4.8.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> x = {"a","b","c","d","e"}
>>> x
{'d', 'a', 'e', 'c', 'b'}
>>> 
bernd@saturn:~$ python3
Python 3.4.0 (default, Apr 11 2014, 13:05:11) 
[GCC 4.8.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> staedte = {'Hamburg', 'München', 'Frankfurt', 'Berlin'}
>>> x = {"a","b","c","d","e"}
>>> x
{'b', 'e', 'c', 'a', 'd'}
>>> 
bernd@saturn:~$ python3
Python 3.4.0 (default, Apr 11 2014, 13:05:11) 
[GCC 4.8.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> staedte = ['Hamburg', 'München', 'Frankfurt', 'Berlin']
>>> x = {"a","b","c","d","e"}
>>> x
{'b', 'a', 'c', 'e', 'd'}
>>> 
>>> print(x)
{'b', 'a', 'c', 'e', 'd'}
>>>