4. Listen

4.7 Kombinatorik

Dieses Kapitel ist ein kleiner Ausflug in die diskrete Mathematik, insbesondere die Mengenlehre. Einige Dinge werden wir aber tatsächlich später brauchen, zum Beispiel um ein Gitter aus Punkten graphisch darzustellen.

Grundbegriff der Mengenlehre ist die Menge, z.B. ${1, 3, True, hello}$ . Typischerweise haben die Objekte in einer Menge den gleichen Typ, Ihnen wird also in der Mathematik so etwas wie ${1, 2, 7, 4}$ begegnen oder ${True, False}$ oder auch ${\sin, \cos, \tan, s q r t}$ und eher nicht so etwas wie ${1, 3, True, hello}$ . Dennoch ist letzteres eine völlig korrekte Menge. Mengen interessieren sich nicht für die Reihenfolgen ihrer Elemente, daher gilt

\begin{array}{r} {1, 4, 5} = {5, 1, 4} \end{array}

und auch nicht dafür, wie oft ein Element genannt wurde, daher

\begin{array}{r} {1, 4, 5} = {1, 4, 4, 5, 1} . \end{array}

Sie interessiert sich nur dafür, welche Elemente überhaupt enthalten sind. Daher gilt

\begin{array}{r} {1, 4, 5} \neq {1, 4, 0, 5}, \end{array}

da die rechte Menge das Element

0

enthält, die linke Menge jedoch nicht. Mengen können selbst wieder Mengen als Elemente enthalten, zum Beispiel

\begin{array}{r} {{1, 2}, 2, {3}, 3} . \end{array}

Dies ist eine Menge aus vier (verschiedenen) Elementen.

Wir können aus zwei Mengen neue Mengen bauen, zum Beispiel

die Vereinigung $A \cup B$ , bestehend aus allen Elementen, die in $A$ oder in $B$ sind (oder in beiden);
die Schnittmenge $A \cap B$ , bestehend aus den Elementen, die sowohl in $A$ als auch in $B$ sind;
die Differenzmenge $A ∖ B$ , bestehend aus den Elementen, die in $A$ sind, aber nicht in $B$ .

Wir haben spezielle Symbole $\in$ oder $\subseteq$ , die folgendes bedeuten:

$x \in A$ bedeutet, dass $x$ ein Element der Menge $A$ ist;
$A \subseteq B$ bedeutet, dass $A$ eine Teilmenge von $B$ ist; dass also jedes Element $x$ , das in $A$ ist, auch in $B$ ist; als logische Formel also, dass $\forall x : x \in A \to x \in B$ gilt.

Manchmal drehen wir die Symbole um und schreiben $A ∋ x$ und $B \supseteq A$ , was das gleiche bedeutet wie $x \in A$ bzw. $A \subseteq B$ . Also beispielsweise $1 \in {1, 2, 3}$ und ${1, 3} \subseteq {1, 2, 3}$ aber ${1, 3, 4} ⊈ {2, 4, 5}$ .

Definition 4.7 (Potenzmenge). Sei $X$ eine Menge. Die Potenzmenge $2^{X}$ ist die Menge aller Teilmengen von $X$ . Also: $A \in 2^{X}$ gilt genau dann, wenn $A \subseteq X$ ist. Insbesondere sind alle Elemente von $2^{X}$ selbst Mengen.

Hier ein Beispiel:

\begin{array}{r} 2^{{1, 4, 5}} = {{}, {1}, {4}, {5}, {1, 4}, {1, 5}, {4, 5}, {1, 4, 5}} \end{array}

Beachten Sie, dass ${} \subseteq {1, 4, 5}$ gilt und auch ${1, 4, 5} \subseteq {1, 4, 5}$ . Daher sind die leere Menge und die Menge $X$ selbst beide Elemente in $2^{X}$ . Für die leere Menge ${}$ wird häufig das Symbol $\emptyset$ verwendet.

Theorem 4.8 Sei $X$ eine endliche Menge aus $n$ Elementen. Dann hat $2^{X}$ genau $2^{n}$ Elemente.

Beweis. Wir verwenden Induktion über $n$ . Wenn $n = 0$ ist, $X$ also 0 Elemente hat, dann ist $X$ die leere Menge, also $X = \emptyset$ . Wieviele Teilmengen hat $\emptyset$ ? Nur sich selbst: $\emptyset \subseteq \emptyset$ . Also gilt $2^{\emptyset} = {\emptyset}$ , was eine Menge mit genau einem Element ist. Daher: $| 2^{\emptyset} | = 2^{0} = 2^{n}$ .

Für den Induktionsschritt haben wir eine Menge $X$ mit $n \geq 1$ Elementen. Nehmen wir ein solches Element $a \in X$ und schreiben $X^{'} := X ∖ {a}$ . Die Menge $X^{'}$ hat $n - 1$ Elemente. Die Teilmengen von $X$ kommen nun in zwei verschiedenen Sorten: die Teilmengen, die $a$ enthalten, und die, die $a$ nicht enthalten. Letztere sind genau die Teilmengen von $X^{'}$ . Da $| X^{'} | = n - 1$ gilt, können wir Induktion anwenden und schließen, dass

Es gibt also genau Teilmengen von , die nicht enthalten. Sei nun die Menge alles Teilmengen von die, enthalten. Es gilt also Wie groß ist nun die Menge ? Wenn das Element enthält, dann tut das nicht, ist also in . Wenn umgekehrt ist, also nicht enthält, dann gilt . Wir können also jedem einen "Partner" in zuweisen und umgekehrt. Daher sehen wir, dass so viele Elemente hat wie , also . Schlussendlich gilt

Die Potenzmenge hat also so viele Elemente, wie behauptet.

Für uns als Programmierer ist nun interessant, wie wir berechnen können. Als Datenstruktur für Mengen verwende ich aus Faulheit den Elm-Typ List. Da spielen zwar Reihenfolge eine Rolle, eine Liste repräsentiert eine Menge also nur unzureichend, aber für unsere jetzigen Zwecke ist es ausreichend. Beachten Sie, dass der induktive Beweis oben (insbesondere die Unterteilung in die Teilmengen, die enthalten und die, die es nicht tun), sich direkt in rekursiven Code übersetzen lässt.

powerSet : List datatype -> List (List datatype)
powerSet list =
    case list of
        [] ->
            [ [] ] -- das entspricht der Menge {{}}

        a :: rest ->
            let
                thoseWithout_a : List (List datatype)
                thoseWithout_a =
                    powerSet rest

                thoseWith_a =
                    List.map ((::) a) thoseWithout_a
            in
            thoseWithout_a ++ thoseWith_a

Ein paar Erklärungen: in Zeile 12-14 berechnen wir , also die Teilmengen, die nicht enthalten. In Zeilen 16-17 berechnen wir , indem wir jedem das Element hinzufügen. Um die Notation List.map ((::) a) thoseWithout_a zu verdauen, müssen Sie vieles von dem hervorholen, das wir in den letzten Kapiteln gelernt haben:

Das :: ist ein Konstruktor für den Custom Type List. Wir schreiben ihn normalerweise in Infixform, so stellt also 4 :: [2,6,7] eine neue Liste [4, 2, 6, 7] her. Wenn wir (::) schreiben, so erhalten wir das gleiche in Präfixform, also (::) 4 [2, 6, 7]. Der Konstruktor (::) hat zwei Parameter als Ladegut: das Element (hier 4) und die Liste, der es vorangestellt werden soll (hier [2, 6, 7]).
Konstruktoren mit Ladegut verhalten sich syntaktisch wie Funktionen. Das (::) hat also Signatur a -> List a -> List a.
Im Ausdruck (::) a füttern wir (::) mit nur einem Argument, hier vom Typ datatype. Es wird also zu einer Funktion mit Signatur List datatype -> List datatype. Was macht diese Funktion? Sie stellt Ihrem Argument (einer Liste) den Wert a voran und erzeugt so eine neue Liste. Wir verwenden hier also Currying.
Im Ausdruck List.map ((::) a) thoseWithout_a wird nun die gecurryte Funktion ((::) a) ("nimm das Argument und klebe a vorne dran) auf jedes Element von thoseWithout_a angewandt. Mengentheoretisch also: aus jedem wird die Menge gebildet.

Nun dürfen Sie es ausprobieren:

type Wer = Ich | Du | Er | Sie
powerSet [Ich, Du, Er, Sie]
[[],[Sie],[Er],[Er,Sie],[Du],[Du,Sie],[Du,Er],[Du,Er,Sie],[Ich],[Ich,Sie],[Ich,Er],[Ich,Er,Sie],[Ich,Du],[Ich,Du,Sie],[Ich,Du,Er],[Ich,Du,Er,Sie]]

Teilmengen bestimmter Größe

Sei eine Menge und eine natürliche Zahl. Mit bezeichnet man die Menge der Teilmengen, die genau Elemente haben. Falls Ihnen schon mal die Notation begegnet ist, so ist die Ähnlichkeit kein Zufall. Mit bezeichnen wir die Anzahl der Teilmengen von , die genau Elemente haben.

Um für eine Menge (in Elm: eine Liste) die Menge (bzw. Liste) zu berechnen, könnten wir bequem vorgehen: wir berechnen die Potenzmenge und filtern dann die Mengen raus, die genau Elemente haben. In Elm ginge das so:

hasLength : Int -> List a -> List a
hasLength k list = List.length list == k
List.filter (hasLength 2) (powerSet [Ich, Du, Er, Sie])
[[Er,Sie],[Du,Sie],[Du,Er],[Ich,Sie],[Ich,Er],[Ich,Du]]

Das geht, ist aber verschenderisch. Es werden erst alle Teilmengen konstruiert, um dann die , die wir wollen, rauszufiltern. Gerade von recht klein ist, ist dies unverhältnismäßig langsam:

List.filter (hasLength 2) (powerSet (List.range 1 20))

liefert zwar das richtige Ergebnis (alle 190 Teilmengen der Größe 2), berechnet aber erst einmal alle Teilmengen. Wir müssen gezielter vorgehen.

Theorem 4.9 Es gilt und falls . Für gilt

Beweis. Die ersten beiden Aussagen sind recht einfach. Für gilt . Diese Menge hat genau eine Teilmenge der Größe 0 (sich selbst), also . Sie hat keine (also 0) Teilmengen der Größe , falls ist, und somit gitl .

Falls gilt, ist und enthält ja zumindest mal das Element . Wir teilen wieder die Teilmengen in zwei Gruppen: (1) diejenigen, die nicht enthalten; (2) diejenigen, die enthalten. Erstere, also Mengen vom Typ (1) sind genau die Mengen in , es gibt also davon. Letzere, also die vom Typ (2), können wir bauen, indem wir Mengen in nehmen (jede davon hat Elemente), und dann jeder das Element hinzufügen (jetzt hat sie Elemente). Es gibt also insgesamt Mengen vom Typ (2). Insgesamt also Mengen der Größe .

Wir können wieder diesem Beweis in Code umsetzen: wenn die Menge (in Elm Liste list) nichtleer ist, also die Form x :: rest hat, dann können wir rekursiv die Teilmengen von rest mit Größe berechnen; in einem zweiten Schritt rekursiv die Teilmengen von rest mit Größe ; letzteren müssen wir aber jeweils noch das Element x voranstellen, was mit List.map ganz einfach geht.

Übungsaufgabe 4.7.1 Implementieren Sie eine Funktion choose : Int -> List a -> List (List a), die die Menge einer Teilmengen gegebener Größe berechnet.

Das Cartesische Produkt

Für zwei Mengen und definieren wir das cartesische Produkt

also die Menge aller geordneten Paare, die sich bilden lassen. Das funktioniert auch wunderbar mit unendlichen Mengen. So sind die Elemente von Paare reeller Zahlen, zum Beispiel , also Punkte in einem zweidimensionalen Raum.

Ich will ich Elm nun eine Funktion cartesianProduct schreiben, die zwei Listen nimmt und eine Liste von Paaren (aller möglicher Paare) zurückgibt. Zum Beispiel:

type Wochentag = Montag | Dienstag | Mittwoch | Donnerstag | Freitag | Samstag | Sonntag                        
wochentage = [Montag, Dienstag, Mittwoch, Donnerstag, Freitag, Samstag, Sonntag]
type Tageszeit = Vormittag | Nachmittag | Abend
tageszeiten = [Vormittag, Nachmittag, Abend]
cartesianProduct wochentage tageszeiten
[(Montag,Vormittag),(Montag,Nachmittag),(Montag,Abend),(Dienstag,Vormittag),(Dienstag,Nachmittag),(Dienstag,Abend),(Mittwoch,Vormittag),(Mittwoch,Nachmittag),(Mittwoch,Abend),(Donnerstag,Vormittag),(Donnerstag,Nachmittag),(Donnerstag,Abend),(Freitag,Vormittag),(Freitag,Nachmittag),(Freitag,Abend),(Samstag,Vormittag),(Samstag,Nachmittag),(Samstag,Abend),(Sonntag,Vormittag),(Sonntag,Nachmittag),(Sonntag,Abend)] : List (Wochentag, Tageszeit)

Wie gehe ich vor? Ich will die erste Liste durchgehen, und für jedes Element x der ersten Liste folgendes tun: ich will es mit jedem Element y der zweiten Liste zu einem Paar (x, y) kombinieren. Tasten wir uns langsam vor:

Tuple.pair Montag Vormittag                        
(Montag, Vormittag) : (Wochentag, Tagezeit)
Tuple.pair Montag
<function> : b -> ( Wochentag, b )
List.map (Tuple.pair Montag) tageszeiten
[(Montag,Vormittag),(Montag,Nachmittag),(Montag,Abend)] : List ( Wochentag, Tageszeit )

Der letzte Ausdruck paart den Wert Montag mit jedem Element der Liste [Vormittag, Nachmittag, Abend]. Genau das wollen wir! Aber nicht nur für Montag, sondern für jedes Element der ersten Liste. Wir brauchen nun tatsächlich eine Helferfunktion pairXwithAllInList:

pairXwithAllInList : List b -> a -> List (a,b)                        
pairXwithAllInList list x = List.map (Tuple.pair x) list
List.map (pairXwithAllInList tageszeiten) wochentage
[[(Montag,Vormittag),(Montag,Nachmittag),(Montag,Abend)],[(Dienstag,Vormittag),(Dienstag,Nachmittag),(Dienstag,Abend)],[(Mittwoch,Vormittag),(Mittwoch,Nachmittag),(Mittwoch,Abend)],[(Donnerstag,Vormittag),(Donnerstag,Nachmittag),(Donnerstag,Abend)],[(Freitag,Vormittag),(Freitag,Nachmittag),(Freitag,Abend)],[(Samstag,Vormittag),(Samstag,Nachmittag),(Samstag,Abend)],[(Sonntag,Vormittag),(Sonntag,Nachmittag),(Sonntag,Abend)]]
    : List (List ( Wochentag, Tageszeit ))

Fast. Aber nicht ganz. Analysieren wir den letzten Ausdruck List.map (pairXwithAllInList tageszeiten) wochentage. Das erste Argument von List.map, also pairXwithAllInList tageszeiten, ist ein unvollständiger Funktionsaufruf und gibt uns daher eine gecurryte Funktion. Sie wartet auf ein a-Element, das sie dann mit jedem Element in tageszeiten zu einem (a, Tageszeit)-Paar verkuppeln kann. Und diese gecurryte Funktion wenden wir nun auf jedes Element in der Liste wochentage an. Leider gibt dies uns eine Liste von Listen zurück. Wir wollen diese noch zu einer großen Gesamtliste verschmelzen. Zwei Listen verknüpft man mittels List.append oder :: oder in Präfixschreibweise (::). Um eine Liste von Listen zu einer großen zu vereinigen, können wir List.foldl verwenden:

List.foldl List.append [] [ [1,2], [3,4], [5,6]]                        
[5,6,3,4,1,2] : List number

Knapp daneben, wenn uns die Reihenfolge wichtig ist. Das liegt nun daran, dass List.foldl das neue Element (zum Beispiel die Liste [3,4]) nimmt und dann als erstes Argument von List.append nimmt, also List.append [3,4] [1,2]. Genau falschrum also. Wir können jedoch einfach List.foldr verwenden:

List.foldr List.append [] [ [1,2], [3,4], [5,6]]
[1,2,3,4,5,6] : List number

oder das vorgefertige List.concat. Dann müssen wir gar nicht nachdenken:

List.concat  [ [1,2], [3,4], [5,6]]                        
[1,2,3,4,5,6] : List number

Zurück zum cartesischen Produkt nun also: da uns List.map (pairXwithAllInList tageszeiten) wochentage eine Liste von Listen von Paaren zurückgibt, müssen wir diese noch verschmelzen:

List.concat (List.map (pairXwithAllInList tageszeiten) wochentage)                        
[(Montag,Vormittag),(Montag,Nachmittag),(Montag,Abend),(Dienstag,Vormittag),(Dienstag,Nachmittag),(Dienstag,Abend),(Mittwoch,Vormittag),(Mittwoch,Nachmittag),(Mittwoch,Abend),(Donnerstag,Vormittag),(Donnerstag,Nachmittag),(Donnerstag,Abend),(Freitag,Vormittag),(Freitag,Nachmittag),(Freitag,Abend),(Samstag,Vormittag),(Samstag,Nachmittag),(Samstag,Abend),(Sonntag,Vormittag),(Sonntag,Nachmittag),(Sonntag,Abend)] : List ( Wochentag, Tageszeit )

Gut, das ist genau das, was wir wollen. Und nun zusammenfassend als Funktion:

pairXwithAllInList : List b -> a -> List ( a, b )
pairXwithAllInList list x =
    List.map (Tuple.pair x) list


cartesianProduct : List a -> List b -> List ( a, b )
cartesianProduct listA listB =
    List.concat (List.map (pairXwithAllInList listB) listA)

und der obligatorische Testaufruf:

cartesianProduct wochentage tageszeiten

In der Mathematik begegnen uns manchmal cartesische Produkte unbegrenzter Länge, also zum Beispiel

Das lässt sich in Elm nicht mehr mit Tupeln bewältigen, denn dann müsste ja im Voraus feststehen. In diesem Setting haben wir also eine beliebige lange Liste aus Listen, also , und wollen das cartesische Produkt, wobei wir jedes Tupel als Liste interpretieren. Der Ergebnistyp ist also wieder eine Liste von Listen.

Ein (wieder etwas weit hergeholtes) Beispiel wäre die Konjugation deutscher Verben (oder schlimmer noch: lateinischer). Da gibt es nämlich Person, Numerus, Tempus und Modus:

personen =
    [ "erste Person", "zweite Person", "dritte Person" ]


numeri =
    [ "Singular", "Plural" ]


tempora =
    [ "Praesens", "Praeteritum", "Perfekt" ]


modi =
    [ "Indikativ", "Konjunktiv" ]

Das erlaubt uns jetzt schöne aussagen wie "Ich müsste" ist der Konjunktiv Präteritum erste Person Singular des Verbs "müssen". Wie bekommen wir alle möglichen Kombinationen? Ich kürze jetzt das lange cartesianProduct ab:

prod = cartesianProduct                        
prod modi (prod tempora (prod personen numeri))
[("Indikativ",("Praesens",("erste Person","Singular"))),("Indikativ",("Praesens",("erste Person","Plural"))),-- ... und so weiter

Ich will aber erstens den Ausdruck nicht so verschachtelt hinschreiben, zweitens will ich als Ausgabetyp keine verschachtelten Tupel sondern einfach eine Listen von Listen, also [["Indikativ", "Praesens" "erste Person", "Singular"], ["Indikativ", "Praesens", "erste Person", "Plural"], ...]. Ich will folgendes eintippen können:

cartesianProductManyLists [modi, tempora, personen, numeri]

Übungsaufgabe 4.7.2 Implementieren Sie eine Funktion cartesianProductManyLists, die aus [list_1, ..., list_k] , also einer List (List a) eine Liste von Listen generiert, welche insgesamt |list_1| * |list_2| * ... * |list_k| Elemente hat, wovon jedes wiederum eine Liste aus vielen a-Elementen ist.

Tip: ich habe hier ingesamt zwei Helferfunktionen gebraucht. Erstens eien Variante von pairXwithAllInList, zweitens eine Variante von cartesianProduct : List a -> List (List a) -> List (List a), die im Prinzip

berechnet, wobei eine List a ist und das zweite Argument, also bereits eine List (List a). Dann schließlich eine Funktion, die die Listen Schritt für Schritt per cartesianProduct kombiniert.

Permutationen

Mathematisch gesehen ist eine Permutation einer Menge

eine Bijektion

. Wenn

eine endliche Menge mit

Elementen ist, dann ist es oft intuitiver, eine Permutation als Bijektion

zu verstehen. Dann entspricht sie nämlich einer Reihenfolge für die Elemente der Menge. Für

zum Beispiel

Diese Permutationen entsprechen also der Reihenfolge ich fahre um dich (links) bzw. dich fahre ich um.

Übungsaufgabe 4.7.3 Schreiben Sie eine Funktion permutations : List a -> List (List a), die alle Permutationen der Eingabeliste berechnet. Als Beispiel:

permutations [1,2,3]                            
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]] : List (List number)

oder eben

List.map (String.join " ") (permutations ["ich", "dich", "fahre", "um"])
["ich dich fahre um","dich ich fahre um","dich fahre ich um","dich fahre um ich","ich fahre dich um","fahre ich dich um","fahre dich ich um","fahre dich um ich","ich fahre um dich","fahre ich um dich","fahre um ich dich","fahre um dich ich","ich dich um fahre","dich ich um fahre","dich um ich fahre","dich um fahre ich","ich um dich fahre","um ich dich fahre","um dich ich fahre","um dich fahre ich","ich um fahre dich","um ich fahre dich","um fahre ich dich","um fahre dich ich"] : List String