Zählen ohne Aufzählen

Jede Zählfrage ist eigentlich eine Frage danach, wie viele Antworten ein Entscheidungsverfahren hat. Eine Art, solche Fragen zu beantworten, kennen Sie schon: eine Schleife schreiben, aufzählen, die Ausgabe ansehen. Das funktioniert, solange die Ausgabe klein ist, und dann hört es vollständig auf zu funktionieren, nicht allmählich. In dieser Lektion geht es darum, die Zahl zu bekommen, ohne die Liste je zu erzeugen.

/* multiplication rule */

  3 starters * 4 mains * 2 desserts  =  24

  plate: 4 letters, 3 digits
  26^4          = 456976
  26^4 * 10^3   = 456976000

  /* addition rule */
  12 routes + 7 routes  =  19 routes

Die Produktregel ist das Fundament, und sie ist wirklich so einfach: kann man eine erste Wahl auf a Arten treffen und danach eine zweite auf b Arten, so kann man das Paar auf a mal b Arten treffen. Zwei Faustregeln halten sie ehrlich. Multiplizieren Sie, wenn die Wahlen nacheinander geschehen; addieren Sie, wenn es Alternativen sind, die nie zusammen auftreten. Fast jeder Zählfehler ist eine dieser beiden Regeln an der Stelle, an die die andere gehört hätte.

/* ordered choice: pile of 10 people, 3 different prizes */

10 choices, then 9, then 8

  P(10, 3)  =  10 * 9 * 8
            =  720

  P(n, r)   =  n! / (n - r)!

Zehn Personen und drei verschiedene Medaillen ergeben siebenhundertzwanzig Möglichkeiten, und die Produktregel allein bringt Sie dorthin: zehn Möglichkeiten für Gold, neun verbleibende für Silber, acht für Bronze. Das ist eine geordnete Auswahl, geschrieben als P von n und r, und die Formel ist ein fallendes Produkt, das nach r Faktoren abbricht, also n Fakultät geteilt durch n minus r Fakultät. Die Zahl ist nur groß, weil die Reihenfolge als Information zählt.

/* unordered choice: same 10 people, 3 identical seats */

  C(n, r)   =  P(n, r) / r!

  C(10, 3)  =  720 / (3 * 2 * 1)
            =  720 / 6
            =  120

Nun lassen wir die Reihenfolge weg. Dieselben drei Personen in anderer Anordnung auf dem Podium sind kein anderes Ergebnis, wenn die Preise gleich sind, sondern eine Gruppe. Jede Dreiergruppe wurde drei Fakultät mal gezählt, einmal pro Anordnung, also korrigiert die Division durch drei Fakultät genau diese Überzählung. Das ist der ganze Grund, warum der Divisor r Fakultät ist und nicht irgendeine andere Korrektur: es ist die Zahl der Anordnungen, die Sie gerade beschlossen haben zu ignorieren. C von 10 und 3 ist 120, sechsmal kleiner als die geordnete Antwort, und die Merkregel lautet: Kombinationen sind Permutationen mit herausgeteilter Reihenfolge.

Das Schubfachprinzip ist das erste Zählargument, das eine garantierte Antwort liefert statt einer wahrscheinlichen. Wenn n Gegenstände in m Fächer gelegt werden und n größer ist als m, enthält ein Fach mindestens zwei. Das ist alles, es ist offensichtlich, und es ist dennoch eines der nützlichsten Werkzeuge der Algorithmenanalyse, weil es aus reinem Zählen Gewissheit erzeugt. Eine echte Anwendung: eine Hashtabelle hat mehr mögliche Schlüssel als Körbe, also sind Kollisionen kein Zeichen einer schlechten Hashfunktion, sondern eine mathematische Gewissheit. Eine gute Hashfunktion verteilt sie gleichmäßig, statt sie zu beseitigen. Jedes Argument der Art, es werde keine Kollisionen geben, weil der Hash gut sei, ist falsch, bevor es beginnt.

Das Schubfachprinzip erklärt auch, warum die Frage, wie viele Menschen man braucht, damit zwei denselben Geburtstag haben, nicht die Frage ist, die alle zuerst beantworten. Man vergleicht die Zahl der Menschen mit der Zahl der Tage und sagt hundertachtzig. Aber die Fächer sind nicht Menschen gegen Tage, sondern Menschenpaare gegen Tage, und die Zahl der Paare wächst quadratisch, während die Zahl der Menschen linear wächst. Bei dreiundzwanzig Menschen gibt es zweihundertdreiundfünfzig Paare, und die Chance auf mindestens eine Übereinstimmung liegt schon bei etwa der Hälfte. Das ist dieselbe Form wie das Kollisionsargument oben, und deshalb ist eine zufällige Kennung mit vierundsechzig Bit in Ordnung, während eine mit sechzehn Bit ein Produktionsvorfall ist.

birthday problem, 365 days

  two people differ:  364 / 365

  23 people:

  C(23, 2)  =  23 * 22 / 2  =  253 pairs

  (364 / 365)^253  =  0.4995
  1 - 0.4995       =  0.5005

  70 people:  1 - (364 / 365)^2415  >  0.999

Lesen Sie die Geburtstagszahlen als Warnung über die Intuition, nicht als Kunststück. Sechzig Menschen ergeben eintausendsiebenhundertsiebzig Paare, und die Chance auf einen gemeinsamen Geburtstag steigt über neunundneunzig Prozent. Daran ist arithmetisch nichts Feinliches; die Überraschung entsteht allein daraus, dass wir paarweise Ereignisse schätzen, als wären sie unabhängig, und das sind sie nicht. Die praktische Fassung für eine Entwicklerin lautet: der Raum der Kollisionen ist quadratisch in der Zahl der Objekte, also liegt die Geburtstagsschranke immer viel niedriger als die naive.

/* brute force, 10^9 steps per second */

n = 1    2!        =  2
n = 10   10!       =  3.6 * 10^6
n = 13   13!       =  6.2 * 10^9    6 seconds
n = 15   15!       =  1.3 * 10^12   22 minutes
n = 18   18!       =  6.4 * 10^15   74 days
n = 20   20!       =  2.4 * 10^18   77 years
n = 25   25!       =  1.6 * 10^25   5 * 10^8 years

Und schließlich: deshalb ist Zählen für Algorithmen wichtig. Eine Permutationssuche über zwanzig Elemente ist nicht zwanzigmal langsamer als eine über ein Element, sondern zwanzig Fakultät, was die Zahl der Sekunden, die das Universum existiert, mit großem Abstand übersteigt. Die Sprünge zwischen den Zeilen unten sind keine glatte Kurve, sondern eine Klippe, und diese Klippe ist der Grund, warum ein bei kleinen Eingaben korrekter Algorithmus bei echten völlig unbrauchbar sein kann. Wenn jemand sagt, ein Problem sei schwer, meint er meist, die Lösung durch rohe Gewalt sei eine Permutationszahl, und keine Hardware ändert das.