{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Diskrete Mathematik\n",
"\n",
"Python bietet diverse Funktionen, um grundlegende Konzepte aus der Kombinatorik umzusetzen.\n",
"Zum Beispiel lassen sich alle Kombinationen von zwei oder mehr Mengen mittels der Funktion `product` bilden, oder geordnete Auswahlen aus einer Liste mit oder ohne zurücklegen treffen.\n",
"\n",
"Dokumentation: [itertools](https://docs.python.org/2/library/itertools.html)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Für die folgenden Beispiele definieren wir uns die folgenden zwei diskrete Mengen (eine Liste ist OK)"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"animals = [\"cat\", \"dog\", \"fish\"]\n",
"owners = [\"susi\", \"tim\", \"franziska\", \"henry\"]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Produktbildung\n",
"\n",
"Alle Kombinationen durchprobieren"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"cat belongs to susi \n",
"cat belongs to tim \n",
"cat belongs to franziska \n",
"cat belongs to henry \n",
"dog belongs to susi \n",
"dog belongs to tim \n",
"dog belongs to franziska \n",
"dog belongs to henry \n",
"fish belongs to susi \n",
"fish belongs to tim \n",
"fish belongs to franziska \n",
"fish belongs to henry \n"
]
}
],
"source": [
"from itertools import product\n",
"for animal, owner in product(animals, owners):\n",
" print(\"%-5s belongs to %-10s\" % (animal, owner))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Kombinationen aus einer Menge ziehen"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"susi \n",
"tim \n",
"franziska \n",
"henry \n"
]
}
],
"source": [
"# Ziehe 1 ...\n",
"from itertools import combinations\n",
"for owner1 in combinations(owners, 1):\n",
" print(\"%-10s\" % (owner1))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"susi tim \n",
"susi franziska \n",
"susi henry \n",
"tim franziska \n",
"tim henry \n",
"franziska henry \n"
]
}
],
"source": [
"# ... ziehe 2 ...\n",
"from itertools import combinations\n",
"for owner1, owner2 in combinations(owners, 2):\n",
" print(\"%-10s %-10s\" % (owner1, owner2))"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"susi tim franziska \n",
"susi tim henry \n",
"susi franziska henry \n",
"tim franziska henry \n"
]
}
],
"source": [
"# ... oder 3 ....\n",
"from itertools import combinations\n",
"for owner1, owner2, owner3 in combinations(owners, 3):\n",
" print(\"%-10s %-10s %-10s\" % (owner1, owner2, owner3))"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"susi tim franziska henry \n"
]
}
],
"source": [
"# ... oder gar 4!\n",
"from itertools import combinations\n",
"for owner1, owner2, owner3, owner4 in combinations(owners, 4):\n",
" print(\"%-10s %-10s %-10s %-10s\" % (owner1, owner2, owner3, owner4))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Kombinationen mit Zurücklegen"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"susi susi \n",
"susi tim \n",
"susi franziska \n",
"susi henry \n",
"tim tim \n",
"tim franziska \n",
"tim henry \n",
"franziska franziska \n",
"franziska henry \n",
"henry henry \n"
]
}
],
"source": [
"from itertools import combinations_with_replacement\n",
"for owner1, owner2 in combinations_with_replacement(owners, 2):\n",
" print(\"%-10s %-10s\" % (owner1, owner2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Permutationen"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"susi tim \n",
"susi franziska \n",
"susi henry \n",
"tim susi \n",
"tim franziska \n",
"tim henry \n",
"franziska susi \n",
"franziska tim \n",
"franziska henry \n",
"henry susi \n",
"henry tim \n",
"henry franziska \n"
]
}
],
"source": [
"from itertools import permutations\n",
"for owner1, owner2 in permutations(owners, 2):\n",
" print(\"%-10s %-10s\" % (owner1, owner2))"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"susi tim franziska \n",
"susi tim henry \n",
"susi franziska tim \n",
"susi franziska henry \n",
"susi henry tim \n",
"susi henry franziska \n",
"tim susi franziska \n",
"tim susi henry \n",
"tim franziska susi \n",
"tim franziska henry \n",
"tim henry susi \n",
"tim henry franziska \n",
"franziska susi tim \n",
"franziska susi henry \n",
"franziska tim susi \n",
"franziska tim henry \n",
"franziska henry susi \n",
"franziska henry tim \n",
"henry susi tim \n",
"henry susi franziska \n",
"henry tim susi \n",
"henry tim franziska \n",
"henry franziska susi \n",
"henry franziska tim \n"
]
}
],
"source": [
"from itertools import permutations\n",
"for owner1, owner2, owner3 in permutations(owners, 3):\n",
" print(\"%-10s %-10s %-10s\" % (owner1, owner2, owner3))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Graphen\n",
"\n",
"[NetworkX](https://networkx.github.io/) ist eine der am weitesten verbreiteten Python-Bibliotheken für Graphentheorie\n",
"mit einer [Menge von Algorithmen](http://networkx.github.io/documentation/latest/reference/algorithms.html).\n",
"\n",
"\n",
"[NetworkX Dokumentation](http://networkx.github.io/documentation/networkx-1.9.1/)\n",
"\n",
"(Eine andere Pythonbibliothek wäre [SageMath / Graph Theory](http://doc.sagemath.org/html/en/reference/graphs/index.html))\n",
"\n",
"Ein Graph ist eine Menge von Knoten und Kanten (Vertices and Edges),\n",
"wobei die Kanten für Verbindungen zwischen den Knoten stehen.\n",
"Es gibt ungerichtete und gerichtete Verbindungen -- letzteres ist dann ein \"gerichteter Graph\".\n",
"Eine Implementierung im Computer besteht nun darin,\n",
"in einer Datenstruktur diese Kanten und Knoten effizient zu verwalten\n",
"und dann darauf aufbauend Algorithmen aus der Graphentheorie anzuwenden.\n",
"\n",
"Bemerkung: Falls die Bibliothek `networkx` nicht installiert sein sollte, so kann man dies entweder in der Kommandozeile oder in Canopy unter Tools → Canopy Terminal mittels\n",
"\n",
" pip install networkx\n",
" \n",
"nachholen."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'1.9.1'"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import networkx as nx\n",
"%matplotlib inline\n",
"nx.__version__"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Hier wird ein einfacher Graph instanziert. Die Knoten sind einige Hauptstädte, die Kanten stellen (Zug-) Verbindungen zwischen ihnen dar. "
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"g1 = nx.Graph()\n",
"\n",
"g1.add_node(\"Wien\")\n",
"g1.add_node(\"Graz\")\n",
"g1.add_node(\"Linz\")\n",
"g1.add_node(\"Salzburg\")\n",
"g1.add_node(\"Innsbruck\")\n",
"g1.add_node(\"Villach\")\n",
"g1.add_node(\"St. Pölten\")\n",
"\n",
"g1.add_edge(\"Graz\", \"Salzburg\")\n",
"g1.add_edge(\"Wien\", \"Salzburg\")\n",
"g1.add_edge(\"Salzburg\", \"St. Pölten\")\n",
"g1.add_path([\"Wien\", \"Graz\", \"Linz\", \"Salzburg\", \"Innsbruck\", \"Villach\"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Plot des Graphen, wobei mit `spring_layout` eine gleichmäßig verteilte Positionierung der Knoten berechnet wird.\n",
"Anschließend werden nicht nur die Knoten und Kanten,\n",
"sondern auch die Namen der Knoten geplottet."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%matplotlib inline\n",
"pos = nx.spring_layout(g1)\n",
"nx.draw_networkx_labels(g1, pos, font_size = 12)\n",
"nx.draw(g1, pos)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ausgehend von diesem Graph lassen sich einige Kennzahlen und Parameter ausrechnen:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ist er zusammenhängend?"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.is_connected(g1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Grad von Graz"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.degree(g1, \"Graz\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Durchmesser des ganzen Graphs"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.diameter(g1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exzentrizität"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{'Graz': 3,\n",
" 'Innsbruck': 2,\n",
" 'Linz': 3,\n",
" 'Salzburg': 2,\n",
" 'St. Pölten': 3,\n",
" 'Villach': 3,\n",
" 'Wien': 3}"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.eccentricity(g1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Kürzester Weg von Linz nach Innsbruck"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"['Linz', 'Salzburg', 'Innsbruck']"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.shortest_path(g1, \"Linz\", \"Innsbruck\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Es gibt außerdem eine große Bibliothek für Graphen.\n",
"Hier wird ein Dodekaedergraph geladen und der 10-te Knoten entfernt."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"g2=nx.dodecahedral_graph()\n",
"g2.remove_node(10)\n",
"nx.draw(g2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Durchmesser"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.diameter(g2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Vergleich der Dichte beider Graphen:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(0.38095238095238093, 0.15789473684210525)"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.density(g1), nx.density(g2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Histogramdaten für die Grade aller Knoten:"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[0, 0, 3, 16]"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.degree_histogram(g2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Gerichteter Graph\n",
"\n",
"Ein **gerichteter Graph** für die Wörter in einem Text."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"text = '''11:15 Restate my assumptions:\n",
"1. Mathematics is the language of nature.\n",
"2. Everything around us can be represented and understood through numbers. \n",
"3. If you graph these numbers, patterns emerge.\n",
"Therefore: There are patterns everywhere in nature.'''"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import re\n",
"words = re.compile(r'[a-zA-Z]+')\n",
"tokens = words.findall(text)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"text_digraph = nx.MultiDiGraph()\n",
"for t1, t2 in zip(tokens[:-1], tokens[1:]):\n",
" text_digraph.add_edge(t1, t2)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%matplotlib inline\n",
"nx.draw(text_digraph, with_labels = True)"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"['Everything',\n",
" 'around',\n",
" 'us',\n",
" 'can',\n",
" 'be',\n",
" 'represented',\n",
" 'and',\n",
" 'understood',\n",
" 'through',\n",
" 'numbers']"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.shortest_path(text_digraph, \"Everything\", \"numbers\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Baum (Tree)\n",
"\n",
"Ein Baum startet bei einem Wurzelknoten und verästelt sich ohne Schleifen zu bilden.\n",
"Knoten ohne Kinder werden Blätter genannt."
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"rtree = nx.balanced_tree(2, 3)\n",
"%matplotlib inline\n",
"nx.draw(rtree)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.is_tree(rtree)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Liste der Blätter-Knoten (Grad ist 1)"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[7, 8, 9, 10, 11, 12, 13, 14]"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[ k for k, v in nx.degree(rtree).items() if v == 1]"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.4.3"
}
},
"nbformat": 4,
"nbformat_minor": 0
}