Donnerstag, 21. Juli 2016

Jenseits von Schere, Stein und Papier

Eine Relation "ist stärker als" modellieren

Vor kurzem stellte sich ein Lernender in der Programmierkunst die Aufgabe, ein Spiel ähnlich dem bekannten Schere, Stein, Papier! zu entwickeln: der Spieler wählt eine "Waffe", danach wählt die Maschine mittels Zufallsgenerator eine. Die Maschine prüft dann, welche Waffe "stärker" ist und gibt aus, wer gewonnen hat.

Die Menge der Waffen abzubilden, war einfach: er entschied sich für einen Array, der einfach eine Liste der verfügbaren Waffen in Form von Strings enthielt:
var weapons = ["pistol","bomb","knife"];
Wie aber sollte er nun - und das war die Frage, mit der er sich ans Forum wandte - die Funktion definieren, die ihm liefert, welche Waffe stärker ist als welche?
function isStronger(weapon1,weapon2) {
  // ???
}
Die Relation "ist stärker als", die er sich dabei als Beispiel gewählt hat, hatte er durch bomb > knife, knife > pistol, pistol > bomb definiert (wie er diese Relation begründen mag, ist ein anderes Thema: siegt die Pistole über die Bombe, weil der treffsichere Pistolero rechtzeitig den Zünder kaputtschießt? Und das Messer siegt über die Pistole, weil der Kämpfer es schneller parat hat? Die Begründungen des klassischen "Stein-Papier-Schere"-Spiels kommen mir da plausibler vor - aber darum geht es hier nicht).

Die von ihm gewählte Relation gehört zu denen, in denen das Spiel überhaupt sinnvoll ist, da es keine stärkste Waffe gibt. Jede Waffe ist unter dieser Relation stärker als eine andere und schwächer als eine andere. Gäbe es stattdessen eine stärkste Waffe, wäre das Spiel langweilig: man müßte nur diese stärkste Waffe wählen und könnte nicht mehr verlieren – allenfalls geht es unentschieden aus, wenn die Maschine (der Zufallsgenerator) dieselbe Waffe gewählt hat.

Wie also wäre die Relation mit Programmcode zu modellieren? Eine einfache Antwort wäre, die unterschiedlichen Fälle mit dem zu Recht unbeliebten switch/case zu programmieren:

function isStronger(weapon1,weapon2) {
  switch(weapon1) {
    case "bomb":
      switch(weapon2) {
        case "bomb":
          return false;
        case "knife":
          return true;
        case "pistol":
          return false;
        default:
          throw new Error('Unknown weapon "'+weapon2+'"')
      }
    case "knife":
      switch(weapon2) {
        case "bomb":
          return false;
        case "knife":
          return false;
        case "pistol":
          return true;
        default:
          throw new Error('Unknown weapon "'+weapon2+'"')
      }
    case "pistol":
      switch(weapon2) {
        case "bomb":
          return true;
        case "knife":
          return false;
        case "pistol":
          return false;
      default:
        throw new Error('Unknown weapon "'+weapon2+'"')
      }
    default:
      throw new Error('Unknown weapon "'+weapon1+'"')
  }
}
Dieser Code, obwohl unglaublich aufgebläht, ist immerhin korrekt, leistet das Gewünschte: er liefert für jedes mögliche Paar von Waffen die Angabe, welche stärker als welche ist.

("Aber ist das nicht das Wichtigste: dass der Code tut, was er soll?" - fragen Leute, die Clean Code und/oder The Pragmatic Programmer nicht gelesen haben...)

Obendrein enthält der Code auch ein Fehlerhandling durch Abfangen der Defaultzweige. Andererseits wird der Array weapons überhaupt nicht benötigt. Es ist alles ausprogrammiert. Die Gefahr von Tippfehlern, wenn weitere Waffen dazukommen, ist erheblich.

Eine übliche Refaktorisierung des switch/case-Statements besteht darin, statt Code eine Datenstruktur zu verwenden und die cases durch Zugriffe auf diese Datenstrukturen mit Index oder mit dem Dot-Operator zu ersetzen.

In diesem Fall könnte das so aussehen:

var isStronger = (function(){
   var stronger = {
     "bomb":{ 
       "bomb":false,
       "knife":true,
       "pistol":false
     }
     "knife":{ 
       "bomb":false,
       "knife":false,
       "pistol":true
     }
     "pistol":{ 
       "bomb":true,
       "knife":false,
       "pistol":false
     }
   }   
   return function(weapon1,weapon2) {
       return stronger[weapon1][weapon2]
   }
})();
Das hält immerhin die benötigte Information ("ist stärker als") vom eigentlichen Code getrennt.
Das Fehlerhandling, auf das es mir hier nicht ankommt, habe ich weggelassen - es wäre leicht nachzutragen: der Zugriff stronger[weapon1][weapon2] liefert den Wert undefined, wenn weapon2 nicht bekannt ist. Er löst die abzufangende Ausnahme TypeError aus, wenn weapon1 nicht bekannt ist (die durch den Zugriff auf das Member weapon2 des Wertes undefined entsteht).

Nun enthält auch dieser Code noch Redundanzen: es ist auch ausprogrammiert, dass eine Waffe nie stärker ist als sie selbst. Ausserdem genügt es offenbar anzugeben, wer stärker ist als wer. Denn aktuell ist jede Relation doppelt enthalten.

Eine Relation wie "ist stärker als" kann in Form einer Matrix modelliert werden, in der jede Zeile für den ersten und jede Spalte für den zweiten Kandidaten im Vergleich steht. Ist der Vergleich positiv, wird an dieser Stelle eine 1 notiert; ist "stärker als" nicht erfüllt, eine 0.
Man muss die Einsen in der Matrix durchgehen, um die Relation auszubuchstabieren. Wenn wir die Relation "ist stärker als" mit dem Symbol ≻ notieren und die "Waffen" durchnumerieren, so codiert die hier dargestellte Matrix also die Relation
  1 ≻ 2
  2 ≻ 3
  3 ≻ 1
Spiegelt man die Matrix an der Hauptdiagonalen, so müssen für alle Plätze außerhalb dieser Hauptdiagonalen Einsen mit Nullen vertauscht werden. Die Plätze auf der Diagonalen sind immer 0 (denn keine Waffe ist stärker als sie selbst). Um zu sagen, welche Waffe stärker als welche ist, sind also nur die Plätze oberhalb der Diagonalen beliebig mit Einsen oder Nullen zu besetzen. Das ist die einzige benötigte Information. Insbesondere gibt es 23 = 8 verschiedene Möglichkeiten, "ist stärker als" auf der Menge mit drei Waffen zu definieren.
Die Entfernung von Redundanz reduziert wieder die Gefahr von Tippfehlern und beschränkt die Information der stronger-Datenstruktur auf das Wesentliche:
var isStronger = (function(){
   var stronger = {
     "bomb":["knife"],
     "knife":["pistol"],
     "pistol":["bomb"]
     }
   }   
   return function(weapon1,weapon2) {
       return stronger[weapon1].indexOf(weapon2) >= 0
   }
})();
Da bei der hier gewählten Relation eine Waffe immer stärker als genau eine andere ist, hätte man für diese konkrete Relation statt eines Hashs of Arrays (HoA) auch dieses Wissen einfließen lassen und einen Hash of Strings wählen können:
var isStronger = (function(){
   var stronger = {
     "bomb":"knife",
     "knife":"pistol",
     "pistol":"bomb"
     }
   }   
   return function(weapon1,weapon2) {
       return stronger[weapon1] == weapon2
   }
})();
Nur ist diese Version leider nicht verallgemeinerbar: es ist absehbar, dass weitere Waffen dazukommen werden. Es ist dann, wie man leicht sehen kann, überhaupt nicht mehr möglich, ein "ist stärker als" zu definieren, in dem jede Waffe stärker als genau eine andere Waffe ist. Der Ansatz mit dem Hash of Arrays ist daher in Hinblick auf die Erweiterbarkeit vorzuziehen.
Wenn wir das konkrete Wissen einfließen lassen wollen, wäre es sowieso viel einfacher. Denn die von ihm gewählte Relation "ist stärker als" ist ja eine ringförmige Anordnung.

Es gewinnt jeweils der, der in diesem orientierten Kreis unmittelbar vor dem anderen liegt. Wenn wir den Array der weapons ins Spiel bringen, lässt sich diese Regel für ist stärker als mit dem Modulo-Operator % implementieren:
function isStronger(weapon1,weapon2) {
  var i1 = weapons.indexOf(weapon1);
  var i2 = weapons.indexOf(weapon2);
  return (3 + i1 - i2) % 3 == 2;
}
Hier steckt also das ganze Wissen um die konkrete Relation "ist stärker" nicht mehr in einer Datenstruktur, sondern in einer Formel. Wenn man die Relation ändert - oder auch nur erweitert, indem man eine neue Waffe hinzufügt, muss man sich eine neue Formel überlegen. Und um die Formel zu verstehen, muss man sie - zugegeben! - etwas gründlicher anschauen als im vorigen Beispiel die Datenstruktur. Andererseits erkennt man an der Verwendung des Modulo-Operators, dass eine zyklische Struktur zugrundeliegt. Bei der expliziten Modellierung mit der Datenstruktur sieht man das erst auf den zweiten Blick.

Klassifizierungsprobleme

Einfache Fragen verlangen oft danach, in einen größeren Zusammenhang gestellt zu werden. "Schere - Stein - Papier" wirft die Fragen auf:
  1. Wie ist überhaupt eine Relation "stärker als" rein formal zu definieren?
  2. Welche Relationen dieser Art gibt es, und wie lassen sie sich beschreiben?
In diesem Blogpost ist die erste Frage - nach dem Begriff dieser Relationen - bereits in natürlicher Sprache beantwortet. Formal können wir von einer Relation im strengen, mengentheoretischen Sinn sprechen, notieren wir sie wieder mit dem Zeichen ≻, die folgende Eigenschaften hat:
  1. Sie ist asymmetrisch, das heißt für zwei beliebige Elemente x, y gilt nie zugleich x≻y und y≻x.
  2. Sie ist total, das heißt zwei beliebige Elemente x, y stehen immer in Relation zueinander: eines von beiden ist "≻" als das andere.
Wir reden also über die asymmetrischen, totalen Relationen auf einer endlichen Menge. Solche Relationen heißen in der Literatur auch Dominanzrelationen. Die beiden Eigenschaften lassen sich zu einer einzigen zusammenfassen:
Für zwei beliebige Elemente x,y der Menge gilt immer genau eine der drei Beziehungen x=y, x≻y oder y≻x.
Solche Relationen werden gelegentlich auch Turnierrelationen genannt, weil jede Relation dem möglichen Ausgang eines Turniers von n Spielern entspricht, wobei jeder Teilnehmer einmal gegen jeden anderen Teilnehmer spielt.
Die zweite Frage ist ein typisches Klassifikationsproblem. Man könnte ja sagen: die Antwort ist: es gibt so viele Relationen dieser Art, wie es Besetzungen des oberen Dreiecks einer n×n-Matrix mit den Werten 0 oder 1 gibt. Da das obere Dreieck einer n×n-Matrix n(n-1)/2 Plätze hat, gibt es also 2n(n-1)/2 mögliche Dominanzrelationen auf der Menge mit n Elementen.

Alles richtig. Aber ist die Frage damit wirklich beantwortet?

Nein: wir wissen nicht, welche dieser Relationen sich nur durch Umbenennung der Elemente unterscheiden. Nehmen wir z.B. die Relation
  1 ≻ 2
  2 ≻ 3
  1 ≻ 3
Sie entspricht folgendem Graphen:
Betrachten wir nun die folgende Relation:
  3 ≻ 2
  2 ≻ 1
  3 ≻ 1
Ist es wirklich eine andere? Wenn wir uns den Graphen ansehen, würden wir sagen: es ist die gleiche, nur wurden die Elemente anders benannt - 3 heißt jetzt 1 und 1 heißt 3:
Insgesamt gibt es auf der dreielementigen Menge 23=8 Dominanzrelationen. Von diesen acht haben aber sechs den gleichen Graphen wie den gerade abgebildeten, entsprechend den 3! = 6 Möglichkeiten, die Elemente 1, 2 und 3 in einer Reihe hinzuschreiben (Permutationen).
Es bleiben zwei weitere Relationen übrig, die aber ebenfalls auseinander durch Vertauschung von Elementen hervorgehen (hierfür müssen genau zwei Elemente miteinander vertauscht werden). Es sind die Relationen, die einer kreisförmigen Anordnung entsprechen. Einerseits diese:
Und andererseits diese:
Wie man sieht, gehen diese beiden Graphen auseinander hervor, wenn man die Elemente 1 und 3 vertauscht. Sie können daher als "die gleiche Relation" betrachtet werden, denn auf die Benennung der einzelnen Elemente kommt es ja nicht wirklich an.

Das ist ein typischer Abstraktionsvorgang in der Mathematik. In diesem Fall operiert die symmetrische Gruppe Sn der Permutationen der n-elementigen Menge auf der Menge aller Dominanzrelationen dieser n-elementigen Menge, nennen wir sie Dn. Das heißt, es gibt eine Abbildung Sn×Dn⟼Dn, die jedem Paar aus einer Permutation pSn und einer Dominanzrelation ≻∈Dn eine neue Dominanzrelation ≻pDn zuordnet, definiert durch

x ≻p y :⟺ p(x) ≻ p(y) für alle Elemente x, y,

wobei die Gruppenoperation verträglich mit der Hinereinanderausführung ist, d.h. es gilt (≻p)q = ≻qp für alle Permutationen p,q und alle Dominanzrelationen .

Die ursprüngliche Menge Dn zerfällt unter der Operation dieser Gruppe in einzelne zueinander elementfremde Teilmengen, deren Elemente jeweils durch die Operation der Gruppe auseinander hervorgehen, die sogenannten Orbits der Gruppenoperation (oder auch: die Äquivalenzklassen bezüglich der Äquivalenzrelation, die durch die Gruppenoperation definiert wird).

Die Frage ist dann: beschreibe für jeden Orbit einen typischen Repräsentanten, am besten durch eine Konstruktionsbeschreibung. Dann könnte man sagen, man hat das Klassifikationsproblem gelöst, "man hat jede Dominanzrelation einmal gesehen".

Im Falle der dreielementigen Menge erzeugt die Operation der symmetrischen Gruppe offensichtlich zwei Orbits. Der eine enthält sechs Relationen, durch die die drei Elemente zu einer Kette angeordnet werden: es gibt jeweils ein größtes Element, ein mittleres und ein kleinstes Element. Der zweite Orbit ist nur zweielementig. Er entspricht der Anordnung der Elemente in einem orientierten Kreis, wobei jedes Element nur "größer" ist als sein direkter Vorgänger im Kreis. Bei der dreielementigen Menge gibt es nur zwei verschiedene Möglichkeiten (entsprechend den Orientierungen), die Elemente in einem Kreis anzuordnen. Daraus gehen die beiden Dominanzrelationen des zweiten Orbits hervor. Tatsächlich sind diese beiden Relationen äquivalent, denn eine beliebige Vertauschung zweier Elemente führt sie ineinander über.

Wie aber sieht es im allgemeinen Fall aus?

Die Ketten

Die Relationen, die ich eben Ketten genannt habe, gibt es für beliebige Grundmengen: man kann sie konstruieren, indem man jedem Element der Menge einen "score" zuweist und dann die Relation durch das "größer als" auf der Zahlenmenge definiert:
function rel(a,b) {
  return score(a) > score(b)
}
Einzige Bedingung, um eine Dominanzrelation zu erhalten, ist daß die verwendete score-Funktion injektiv sein muß: verschiedene Elemente müssen auch verschiedene Scores haben (für Elemente a,b mit gleichem Score wäre die Totalität verletzt, es würde weder a≻b noch b≻a gelten).

Durch die Score-Funktion kommen die Elemente in Form einer Kette auf dem Zahlenstrahl zu liegen, und die Reihenfolge, in der sie auf dem Zahlenstrahl liegen, bestimmt bereits die Relation. Es würde also reichen, Score-Funktionen in die Zahlenmenge {1,2,3,...,n} zu betrachten. Die Abbildung in diese Menge ist dann sogar bijektiv. Die Menge der möglichen Abbildungen entspricht der Menge der Permutationen, der symmetrischen Gruppe Sn.

Bei Ketten gibt es ein Element, das größer als alle anderen ist, dann ein zweitgrößtes Element usw. Die Dominanzrelation läßt sich symbolisch so notieren wie dieses Beispiel:

5 > 6 > 1 > 7 > 3 > 2 > 4

Die Dominanzrelation ≻ ergibt sich dann als transitive Hülle dieser Kette, indem man a≻b setzt, wenn a weiter links als b auf der Kette liegt.

Das bedeutet, mit Hilfe von Score-Funktionen landen wir nur in einer einzigen Äquivalenzklasse, einem einzigen Typ von Dominanzrelationen, dem einfachst möglichen. Die durch Score-Funktionen definierten Dominanzrelationen sind alle untereinander äquivalent.

Notation

Eine Dominanzrelation ist durch die Stellen im oberen Dreieck ihrer darstellenden Matrix definiert, die mit einer Eins besetzt sind. Das gibt eine Möglichkeit, sie in eindeutiger Form zu notieren:
{i1:j1 i2:j2 ... ik:jk}
Dabei sind i1,i2,... die Zeilennummern und j1,j2,... die Spaltennummern der Stellen, an denen in der Matrix eine 1 steht. Diese Stellen sollen nach aufsteigender Zeilennummer und in einer Zeile nach aufsteigender Spaltennummer notiert sein. Dann fungiert der so gebildete String als eindeutige Charakterisierung der Relation: haben zwei Dominanzrelationen einen zeichenweise übereinstimmenden String, so sind sie identisch.
Wenn wir nun zur Informatiker-Konvention übergehen und mit der Null statt der Eins zu zählen beginnen, so steht zum Beispiel die Notation
{0:3 0:5 1:4}
für folgende Dominanzrelation auf der sechselementigen Menge {0,1,2,3,4,5}:
Die Notation {0:3 0:5 1:4} ist also die Kurzform für die Relation
  1>0
  2≻0
  0≻3
  4≻0
  0≻5
  2≻1
  3≻1
  1≻4
  5≻1
  3≻2
  4≻2
  5≻2
  4≻3
  5≻3
  5≻4
Man kann diese Notation so verstehen, dass man genau die "überraschenden" dieser fünfzehn Relationspaare notiert - genau diejenigen, die nicht der normalen "Grösser-als"-Relation unter den natürlichen Zahlen entsprechen.

Differenzrelationen

Das Stein-Papier-Schere-Beispiel suggeriert ein Konstruktionsverfahren für gewisse totale asymmetrische Relationen beliebiger Ordnung, die ich Differenzrelationen nennen möchte.
Wie oben beschrieben, kann man die Stein-Papier-Schere-Relation auf die Subtraktion der Indices reduzieren, die Funktion lässt sich wie folgt hinschreiben:
function isStronger(i,j) {
  return (3 + i - j) % 3 == 2;
}
Die Relation auf der dreielementigen Menge {0,1,2} wird also auf die Subtraktion wie folgt zurückgeführt
i ≻ j :⇔ i - j ∊ { -1,2 }
Das lässt sich verallgemeinern: Auf der n-elementigen Menge {0,1,...n-1} kann man Relationen der Art
i ≻ j :⇔ i - j ∊ S
definieren, wobei die Menge S eine Teilmenge der Menge aller möglichen Differenzen D := { -(n-1),-(n-2),...,-1,0,1,...n-1} ist mit folgenden Eigenschaften:
  • Es gilt S∩-S=∅ (insbesondere muss also 0∉S sein), sonst wäre die Relation nicht asymmetrisch,
  • und es gilt S∪-S∪{0} = D, sonst wäre die Relation nicht total.
Jede derartige Menge S enthält also genau n-1 Elemente und ist von der Form
S = { ±1, ±2, ..., ±(n-1) },
wobei die Vorzeichen frei wählbar sind. Die 2n-1 möglichen Wahlen der Vorzeichen ergeben also ebensoviele verschiedene (aber nicht notwendig inäquivalente) Relationen, die ich mit Δ("vorzeichenfolge") notiere. Z.B. steht
Δ(-+-++)
für die Relation
i ≻ j :⇔ i - j ∊ {-1,2,-3,4,5}
auf der sechselementigen Menge {0,1,2,3,4,5}.

Relationen kombinieren

Man kann Relationen immer aus Relationen niedriger Ordnung konstruieren wie folgt:
  1. Man zerlegt die Grundmenge in k einzelne Teilmengen
  2. Auf jeder dieser k Teilmengen wählt man eine Relation Ri, i=1,...,k
  3. Weiter wählt man eine Relation R auf der Menge mit k Elementen.
  4. Auf der Gesamtmenge definiert man nun, dass x in Relation zu y steht, falls
    • sie beide in der i-ten Teilmenge liegen und sie dort in der Relation Ri stehen,
    • oder sie in verschiedenen Teilmengen i und j liegen, und i und j in der Relation R stehen
Jede der k Teilmengen wird also aus Sicht von R als "ein Element" aufgefasst. Aber innerhalb der einzelnen Teilmengen gelten die Relationen Ri.
Kombinierte Relationen dieser Art notiere ich in der Form
C( R1(i11,i12,...i1n1) R2(...) ... | R(k) )
Dabei stehen R1, ... Rk, R für die Relationen in der oben beschriebenen Notation. Hinter jeder der Einzelrelationen Ri wird die (angeordnete) Folge der Ziffern angeführt, auf denen sie operiert.
So steht z.B. die Notation
C({0:4 0:5 1:5}(0,1,3,4,5) {}(2)|{0:1}(2))
für diese Relation:
Wie man sieht, lassen sich die Ziffern {0,1,3,4,5} zu einer Gruppe zusammenfassen, die kollektiv zum verbleibenden Element 2 in der Relation ≻ steht.
Die Objekte eines Klassifikationsproblems, die sich auf schon bekannte Objekte zurückführen lassen - wie die kombinierten Relationen - sind weniger interessant als die übrigbleibenden, nicht zusammengesetzten, die "einfachen" oder "irreduziblen" Objekte.

Eine Invariante: die Kardinalität

Kennzahlen, die sich bei einem Klassifikationsproblem unter der Gruppenoperation nicht verändern, nennt man Invarianten. Für Relationen kann man eine "Kardinalität" definieren:
Die Kardinalität (0:i0 1:i1... (n-1):in-1) notiert die Anzahlen der Elemente, die in Relation zu keinem, zu einem, zu zwei usw. Elementen stehen.
Zum Beispiel hat die obige kombinierte Relation die Kardinalität
(0:1 3:5),
was bedeutet: ein Element (nämlich die 2) ist nicht grösser als irgendein anderes, alle übrigen Elemente sind grösser als genau drei andere Elemente.
Für diese Anzahlen spielt es offensichtlich keine Rolle, wie die einzelnen Elemente benannt sind oder ob man sie umbenennt.

Das kann man ausnutzen, um schnell zu ermitteln, dass zwei Relationen nicht äquivalent sind: wenn sie verschiedene Kardinalitäten haben, können sie nicht äquivalent sein.

Gilt auch umgekehrt, dass zwei Relationen mit gleicher Kardinalität zueinander äquivalent sind? Für die obige Kardinalität ist das so: es gibt 144 Relationen der Kardinalität (0:1 3:5), und sie sind alle äquivalent zu der gezeigten.

Die Kardinalität bestimmt eine Relation bis auf Äquivalenz aber nur auf Mengen mit bis zu vier Elementen. Schon bei fünfelementigen Mengen gilt das nicht mehr: so haben zum Beispiel die Relationen Δ(+++-) und Δ(+---) zwar dieselbe Kardinalität, nämlich (1:2 2:1 3:2), sind aber nicht zueinander äquivalent.
Wären diese beiden Relationen äquivalent, müsste es eine Permutation geben, die die beiden Graphen ineinander überführt. Dabei müsste die 2 in die 2 abgebildet werden, denn sie ist jeweils das eindeutig bestimmte Element, das genau über zwei andere Elemente dominiert. Die 2 aber bildet rechts (in Δ(+---)) einen Dreierzyklus mit 4 und 3:
2≻4
4≻3
3≻2
Aufgrund der Äquivalenz müssten 4 und 3 zwei Elementen im linken Graphen (dem von Δ(+++-)) entsprechen, die ebenfalls mit der 2 einen Dreierzyklus bilden. Dort gibt es aber keinen Dreierzyklus, der die 2 enthält. Also sind die beiden Relationen inäquivalent, obwohl sie dieselbe Kardinalität haben.

Die Zykelzahl

Invarianten findet man in diesem Problem, indem man Eigenschaften des Graphen zu beschreiben versucht, die nicht von der konkreten Benennung der Elemente abhängen.

Neben der Kardinalität ist beispielsweise auch die Zykelzahl eine Invariante: man kann die Anzahl wirklich verschiedener Dreierzyklen (wie "Papier,Stein,Schere") zählen, die Zahl der Viererzyklen usw. "Wirklich verschieden" bedeutet dabei: bis auf zyklische Vertauschung der zur Beschreibung des Zyklus verwendeten Elemente. "Papier,Stein,Schere" bezeichnet denselben Zyklus wie "Stein,Schere,Papier" oder "Schere,Papier,Stein" – in einem Zyklus ist es ja egal, bei welchem Punkt ich mit der Aufzählung seiner Elemente beginne.

Auch die so gewonnene Zykelzahl ist eine Invariante. Es zeigt sich, dass die Invariante zwar häufig auch verschiedene Äquivalenzklassen gleicher Kardinalität noch auseinanderhalten kann. Bis zu N=5 ist jede Äquivalenzklasse durch Kardinalität und Zykelzahl eindeutig beschrieben. Ab N=6 reicht aber auch die Zykelzahl nicht mehr aus. So haben beispielsweise die Relationen {0:2 0:5} und {0:2 0:3 0:5} dieselbe Kardinalität (1:2 2:1 3:1 4:2) und dieselbe Zykelzahl (3:4 4:4 5:3 6:1), also vier Dreier-, vier Vierer-, drei Fünfer- und einen Sechserzyklus, sind aber nicht zueinander äquivalent.

Ergebnisse

Wie sieht nun die Klassifikation der totalen asymmetrischen Relationen aus? Je mehr Elemente die Grundmenge hat, desto unübersichtlicher wird die Lage natürlich.
Auf der Menge mit N=3 Elementen gibt es, wie schon diskutiert, 6 = 3! zueinander äquivalente "Ketten", also Relationen, die sich von einer Stärkefunktion ableiten lassen. Dazu kommen zwei zueinander äquivalente Relationen vom "Stein-Papier-Schere"-Typ, die sich als Differenzrelation Δ(+-) (oder Δ(-+)) konstruieren lassen. Diese haben die Eigenschaften, dass alle Elemente immer grösser als genau ein anderes Element sind:
Die Kardinalität definiert hier noch eindeutig die Äquivalenzklasse. Das ist auch für N=4 noch der Fall. Dort gibt es bereits vier Äquivalenzklassen, neben den 24 = 4! Ketten gibt es eine Klasse mit 24 Relationen, die auch die Differenzrelation Δ(--+) enthält, sowie zwei weitere Klassen mit je acht Elementen, die sich als zusammengesetzte Relationen darstellen lassen:
Auch für N=5 Elemente können wir noch alle zwölf Äquivalenzklassen von Relationen durch eines der beschriebenen Konstruktionsverfahren repräsentieren - als Kette, als Differenzrelation, oder als zusammengesetzte Relation aus Relationen niederer Ordnung. Hier tritt erstmals der Fall auf, dass die Kardinalität nicht mehr eindeutig die Äquivalenzklasse definiert:
Für N=6 gibt es bereits 56 Äquivalenzklassen. Hier treten erstmals Relationen auf, die sich nicht durch eines der beschriebenen Konstruktionsverfahren herstellen lassen, zum Beispiel die bereits oben behandelte Relation {0:3 0:5 1:4}, oder die Relation {0:2 0:5 1:3}, die in ihrer Komplexität schon ein bisschen an den kabbalistischen Baum der Sephiroth denken lässt. Vielleicht lässt sie sich ja durch ein anderes Produktionsverfahren darstellen?

Wer die Listen dieser Relationen auch für N=6 oder N=7 (Vorsicht, ca. 100 Sekunden Rechenzeit für N=7, es müssen ca. 40 Millionen Äquivalenzprüfungen durchgeführt werden) studieren will, für den habe ich einen Relationsrechner in JavaScript implementiert und hier online gestellt:

http://ruediger-plantiko.net/relations/
Die Implementierung repräsentiert Relationen mit Hilfe von Bitfeldern der Länge N*(N-1)/2.

Die Folge

1,2,4,12,56,456,6880,191536,9733056,...
der Anzahl der Äquivalenzklassen von Dominanzrelationen definiert die OEIS-Zahlenfolge A000568. Unter diesem Link gibt es weitere Informationen und Literaturhinweise.

Nachtrag am 31.7.2016 - die ganze Chose in C++

Meine JavaScript-Implementierung zur Erforschung der Dominanzrelationen auf http://ruediger-plantiko.net/relations/ läuft bis zu N=6 befriedigend schnell; danach explodieren die Laufzeiten relativ rasch. Mit N=7 kommt man noch in ca. einer Minute durch. N=8 habe ich nicht mehr ausprobiert. Liegt es an der Scriptsprache JavaScript, die für solche Algorithmen eher ungeeignet ist? Die Frage liess mir keine Ruhe, und so reimplementierte ich das ganze in C++ - hier der Code auf ideone.com:
http://ideone.com/KBihCA
Das Ergebnis stellte klar: auch mit C++ liess sich die Laufzeit nur ungefähr um den Faktor 3 verbessern. Vielleicht ist, wenn man weitere Optimierungsideen anwendet, auch ein Faktor 10 noch denkbar. Aber das rettet uns nicht. Auch das C++-Programm ist chancenlos für die rund 35 Billionen Relationen (genauer: 245 = 35'184'372'088'832), die für N=10 gegenseitig auf Äuivalenz zu prüfen wären und schließlich 9'733'056 Äquivalenzklassen ergeben werden.

Eine Laufzeitanalyse mit gprof zeigt das erwartbare Ergebnis, dass weit über 95% der Laufzeit im Test auf Äquivalenz liegen - auf diese Prüfung kommt es natürlich an. Meine Optimierung ging schon dahin, statt sämtliche N! Permutationen auszuprobieren, um eine zu finden, die die Relationen ineinander überführt,

  • zuerst die Kardinalitäten der beiden Relationen zu berechnen (da eine der beiden Relationen aus dem Pool der Repräsentanten bereits ermittelter Äuivalenzklassen stammt, muss sie für diese nicht immer neu berechnet werden);
  • sind diese ungleich, so sind die Relationen inäquivalent;
  • sind sie gleich, so muss die Permutation die Elemente mit jeweils gleicher Kardinalität ineinander überführen;
  • ich versuche daher sukzessive die einzelnen Elemente mit Kardinalität 1, 2, usw. durch Permutation so ineinander zu überführen, dass auf den bislang bereits untersuchten Elementen beide Relationen miteinander übereinstimmen. Sobald dies für irgendeine Kardinalität nicht mehr funktioniert, sind die Relationen inäquivalent.
  • erst wenn sie all diese Prüfungen bestanden haben, sind sie äquivalent.

Aber ich habe natürlich den direkten brute force Zugang gewählt. Wenn es nur um die Konstruktion dieser Äuivalenzklassen mit Angabe je eines Repräsentanten geht, ist es vermutlich nicht nötig, sämtliche möglichen Relationen durchzugehen.

2 Kommentare :

Enno hat gesagt…

Hallo Rüdiger,
vielen Dank wieder einmal für einen tollen Artikel!

Ich möchte ja nicht wissen, wie lang der Artikel wird, wenn man zu dem "zirkulären Waffensystem" noch eine Skala berücksichtigt.

Wenn es also Waffen gibt, die gleichwertig sind und bei denen es auf auf so beliebte Attribute wie "Geschicklichkeit", "Kraft", "Durchhaltevermögen" und "Gesundheitszustand" ankommt.

Oder noch schlimmer, eine Waffe nur mit bestimmten Voraussetzungen stärker ist als eine andere:
- Anzahl Trainingseinheiten mit dieser Waffe
- Kraft (Wenn eine Waffe so schwer ist, dass ich sie erst ab einer bestimmten Stärke anheben kann...)
- Oder die Kombination mit einer anderen Waffe, die verwendet wird (Wenn der Gegner eine Bombe hat, ist diese zwar schwächer, als meine Pistole, aber wenn der Gegner zwei Bomben hat, sind diese stärker, weil ich nämlich nur einen Zünder schnell ausschießen kann

Aber wahrscheinlich sind das komplexe Regelsysteme, die einen komplett anderen Ansatz benötigen...?!

Gruß
Enno

Rüdiger Plantiko hat gesagt…

Hallo Enno,

danke für Deinen Kommentar! Natürlich, die tatsächliche Entscheidung, wer in einem Kampf z.B. bei "World of Warcraft" gewinnt, ist viel komplexer als nur die "einfache" Frage, wie man auf einer Menge mit N Elementen eine Relation "A ist stärker als B" definieren kann. Oh wait - habe ich "einfach" gesagt? Schon diese Frage wird, wie man sieht, bei wachsendem N schnell sehr kompliziert. Trotzdem ist es ein interessantes Thema, weil es im Grenzbereich von Informatik und Mathematik liegt. Man kann das Problem von beiden Seiten beleuchten. Wie kann man z.B. einen Algorithmus finden, der möglichst effizient ermittelt, ob zwei gegebene Relationen äquivalent sind, also sich nur durch Umbenennung der Elemente unterscheiden. Das wäre ein Informatikproblem. Oder man kann sich die Frage stellen, was für Konstruktionsverfahren es für Dominanzrelationen geben könnte. Bis N=5 komme ich mit den angegebenen Konstruktionen "Differenzrelation" und "Kette" noch durch. Aber bei N=6 klaffen bereits Lücken, für die ich keine Konstruktion angeben könnte. Obwohl es vermutlich eine gibt - und sie vielleicht auch schon bekannt ist, das Thema wurde schon vor Dekaden mathematisch untersucht. Wenn man das weiterverfolgen wollte, müsste man die o.a. Literaturangaben einmal durcharbeiten - was ich selbst nicht gemacht habe.

Beste Grüsse aus dem Urlaub in Nowogard (ehemals Naugard), Polen!
Rüdiger