Spezielle Abzählprobleme: Ziehen ohne Zurücklegen

Das Abzählproblem "Ziehen ohne Zurücklegen" wird unter der Annahme betrachtet, dass sich in der Urne zwei Arten von Objekten befinden (etwa K Nieten und L Treffer). Berechnet wird die Anzahl der möglichen Ergebnisse, wenn N-mal ein Los aus der Urne gezogen wird und dabei die Reihenfolge der Ergebnisse beachtet wird. Ebenso wird gezeigt, wie man die möglichen Ergebnisse mit Hilfe des Hamming-Abstandes charakterisieren und mit Hilfe des N-dimensionalen Hyperwürfels und im Pascalschen Dreieck veranschaulichen kann. In den R-Skripten werden Algorithmen für das Abzählproblem und die Berechnung der möglichen Ergebnisse vorgestellt und diskutiert.

walter

20 Juni 2021

Abzählprobleme Hyperwürfel Binomialkoeffizient Ziehen ohne Zurücklegen Dualzahl Pascalsches Dreieck Hamming-Abstand combn()Rekursion Ziehen mitZurücklegen Kombinatorik

Inhaltsverzeichnis

Einordnung des Artikels

Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
- Wahrscheinlichkeitsrechnung
  - Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik
  - Grundbegriffe der Wahrscheinlichkeitsrechnung: Binomialkoeffizienten, das Pascalsche Dreieck und der n-dimensionale Hyperwürfel
  - Spezielle Abzählprobleme: Ziehen ohne Zurücklegen

Vorausgesetzt werden hier die Kenntnisse über Binomialkoeffizienten und das Pascalsche Dreieck aus Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik und Grundbegriffe der Wahrscheinlichkeitsrechnung: Binomialkoeffizienten, das Pascalsche Dreieck und der n-dimensionale Hyperwürfel

Die Problemstellung und Bezeichnungen

Im folgenden wird eine Urne betrachtet, die zwei Arten von Kugeln enthält, etwa rote und blaue Kugeln (siehe Abbildung 1 oben für das Beispiel K = 3 und L = 2). Die Anzahl der roten Kugeln werde mit K bezeichnet, die der blauen Kugeln mit L; insgesamt enthält die Urne K + L = M Kugeln.

Oft stellt man sich statt der Kugeln in einer Urne vor, dass es sich um einen Lostopf mit insgesamt M Losen handelt, darunter sind K Nieten (0) und L Treffer (1), siehe Abbildung 1 (Mitte). Die Bezeichnungen 0 und 1 für die Nieten und Treffer wird im Folgenden stets verwendet.

Abbildung 1: In einer Urne befinden sich rote und blaue Kugeln, man kann sich auch einen Lostopf mit Nieten (0) und Treffern (1) vorstellen. Aus dem Lostopf werden nacheinander N Lose ohne Zurücklegen gezogen. Die Tabelle unten zeigt alle möglichen Ergebnisse im Fall K = 3 Nieten, L = 2 Treffer und N = 5 Ziehungen. Dabei werden zwei Ergebnisse als unterschiedlich angesehen, wenn sie sich in der Reihenfolge der gezogenen Lose unterscheiden (siehe etwa zweite und dritte Spalte der Tabelle).

Aus der Urne werden nacheinander Kugeln gezogen, wobei die gezogenen Kugeln nicht zurückgelegt werden.

Mit N wird stets die Anzahl der Ziehungen bezeichnet; und da die Kugeln nicht zurückgelegt werden, kann N nicht größer sein als M = K + L.

In der Tabelle in Abbildung 1 unten sind die 10 Möglichkeiten dargestellt, wenn aus der Urne 5 Kugeln gezogen werden und dabei die Reihenfolge beachtet wird. In der Tabelle zählt die erste Zeile die möglichen Ziehungen; jede der möglichen Ziehungen ist dann in einer Spalte dargestellt.

Damit ist schon ein Spezialfall des Abzählproblems gelöst, das hier allgemein – also mit beliebigen K,L, N – behandelt werden soll.

Abzählproblem:

Gesucht ist die Anzahl der möglichen Ergebnisse, wenn aus der Urne (mit K Nieten und L Treffern) N Lose ohne Zurücklegen gezogen werden, wobei die Reihenfolge der Ziehungen beachtet wird.

Diese gesuchte Anzahl wird im Folgenden mit A(K, L, N) bezeichnet, wobei ohne Einschränkung angenommen werden kann, dass K ≥ L (andernfalls muss man nur die Nieten und Treffer umbenennen).

Um im Folgenden weniger Fallunterscheidungen betrachten zu müssen, wird der triviale Fall L = 0 ausgeschlossen. Denn dann befinden sich nur Nieten im Lostopf und die Lösung des Abzählproblems ist eindeutig.

Ein Beispiel zur Einführung

Das Beispiel aus Abbildung 1, also der Lostopf mit K = 3 Nieten und L = 2 Treffern soll nun näher untersucht werden. Dazu soll die Anzahl N der Ziehungen die Werte N = 1, 2, ..., 5 annehmen; es sollen wie in Abbildung 1 alle möglichen Ergebnisse aufgelistet werden.

Dabei ist klar:

Mehr als 5 Ziehungen muss man nicht betrachten, da die Urne nur 5 Lose enthält.
Es macht keinen Unterschied, ob man N = 4 oder N = 5 setzt, da sich nach der vierten Ziehung nur noch ein Los im Lostopf befindet und daher das Ergebnis der letzten Ziehung feststeht. (Somit kann man in der Tabelle in Abbildung 4 einfach die letzte Zeile weglassen und erhält die möglichen Ergebnisse für N = 4.)

Abbildung 2 zeigt die Tabellen mit den 2, 4, 7, 10, 10 Ergebnissen zu N = 1, 2, ..., 5.

Abbildung 2: Es wird wieder das Abzählproblem zum Ziehen ohne Zurücklegen zu K = 3 und L = 2 betrachtet. Die Tabellen zeigen die möglichen Ergebnisse für N = 1, 2, ..., 5 Ziehungen.

Es ist naheliegend zu fragen, wie man die Anzahl der möglichen Ergebnisse berechnet, wenn man von N zu N+1 übergeht (und K, L unverändert lässt). In der Zahlenfolge 2, 4, 7, 10, 10 sind aber schwer weitere Regelmäßigkeiten zu erkennen als diejenigen, die oben beschrieben wurden.

Die folgende Abbildung 3 zeigt die ersten 6 Zeilen des Pascalschen Dreiecks und wie sich daraus die gesuchten Anzahlen aus Abbildung 2 gewinnen lassen. In den folgenden Abschnitten wird dann gezeigt, wie man den in Abbildung 3 behaupteten Zusammenhang zwischen der Funktion A(K, L, N) und dem Pascalschen Dreieck begründen kann. Es wird sich zeigen, dass man dazu nur eine geeignete Darstellung der möglichen Ergebnisse – also der Spalten in den Tabellen in Abbildung 2 – finden muss.

Abbildung 3: Das gelb hinterlegte Rechteck zeigt, wie man die gesuchten Anzahlen A(K, L, N) berechnen kann. Addiert man in der N-ten Zeile des Pascalschen Dreiecks die Binomialkoeffizienten innerhalb des gelben Rechtecks, so erhält man die Anzahl A(K, L, N). Die Zahlen K und L bestimmen, wie das das Rechteck in das Pascalsche Dreieck eingefügt wird.

Aufgabe: Formulieren Sie, wie die Zahlen K und L die Lage des gelben Rechtecks in Abbildung 3 festlegen.

Die Lösung des Abzählproblems

Vergleich mit "Ziehen mit Zurücklegen"

Werden die Lose mit Zurücklegen gezogen, sind die Anzahlen K und L irrelevant, da in jedem Zug sowohl eine Niete als auch ein Treffer gezogen werden kann. Die Lösung des Abzählproblems hängt jetzt nur von N ab: Da bei jedem Zug 2 Möglichkeiten bestehen, gibt es insgesamt 2^N Möglichkeiten. Und jede dieser Möglichkeiten lässt sich durch eine N-stellige Dualzahl beschreiben.

Diese Überlegung zeigt sofort, welche Fallunterscheidung relevant ist, um das Abzählproblem zu lösen – es sei daran erinnert, dass K ≥ L ≥ 1 vorausgesetzt wurde (mehr Nieten als Treffer):

Für 1 ≤ N ≤ L wird das Abzählproblem gelöst durch A(K, L, N) = 2^N.
Für L < N ≤ K muss berücksichtigt werden, dass der Lostopf eventuell keine Treffer mehr enthält; dagegen kann eine Niete in jedem Zug gezogen werden.
Für K < N ≤ M = K + L muss berücksichtigt werden, dass sowohl die Treffer als auch die Nieten ausgehen können.

Im nächsten Unterabschnitt wird gezeigt, wie man durch eine geeignete Umformulierung des Problems für den zweiten und dritten Fall die gesuchte Anzahl A(K, L, N) berechnen kann.

Beschreibung der Ergebnisse durch Dualzahlen und dem Hamming-Abstand

Betrachtet man die Tabellen in den Abbildungen 1 und 2, so ist klar, dass man das Ergebnis bei N Ziehungen durch eine N-stellige Dualzahl beschreiben kann und die letzte Überlegung zeigt, welche Fallunterscheidung zu beachten ist.

1. Fall: 1 ≤ N ≤ L

Im Fall 1 ≤ N ≤ L sind die möglichen Ergebnisse bei N Ziehungen sämtliche N-stellige Dualzahl, von denen es A(K, L, N) = 2^N gibt, siehe Gleichung (6) in Abbildung 4. (In den Abbildungen 2 und 3 ist dieser Fall für N = 1 und N = 2 eingetreten.)

2. Fall: L < N ≤ K

Im Fall L < N ≤ K kommen nicht mehr alle N-stelligen Dualzahlen in Frage, sondern nur diejenigen, in denen die Anzahl der Einsen die Werte 0, 1, ..., L annehmen kann. In Grundbegriffe der Wahrscheinlichkeitsrechnung: Binomialkoeffizienten, das Pascalsche Dreieck und der n-dimensionale Hyperwürfel wurde gezeigt, dass man die Menge der Dualzahlen mit einer Einschränkung an die Anzahl der Nullen (beziehungsweise Einsen) durch den Hamming-Abstand d_H beschreiben kann (Gleichung (1) in Abbildung 4). Genauer:

Jede N-stellige Dualzahl mit genau k Einsen hat den Hamming-Abstand k von d₀ = (0, 0, ..., 0).
Die Anzahl der N-stelligen Dualzahlen mit genau k Einsen wird durch den Binomialkoeffizienten "k aus N" (siehe auch Gleichung (2) in Abbildung 4).

Für die Anzahl der in zweiten Fall gesuchten Dualzahlen erhält man Gleichung (7) in Abbildung 4.

Abbildung 4: Die Definition des Hamming-Abstandes zweier Dualzahlen. Die Anzahl der N-stelligen Dualzahlen mit genau k Einsen wird durch den Binomialkoeffizienten "k aus N" beschrieben. Damit lässt sich das oben gestellte Abzählproblem für die drei relevanten Fälle lösen.

3. Fall: K < N ≤ M = K + L:

Im Fall K < N ≤ M = K + L gibt es sowohl eine Einschränkung an die Anzahl der Nullen als auch an die Anzahl der Einsen: Als Ergebnisse der N Ziehungen kommen nur Dualzahlen in Frage, in denen die Anzahl der Einsen die Werte 0, 1, ..., L und zugleich die Anzahl der Nullen die Werte 0, 1, ..., K annehmen kann. Letzteres wird mit der Anzahl der Einsen formuliert, um den Hamming-Abstand einzuführen: Gesucht sind die Dualzahlen, in denen die Anzahl der Einsen die Werte 0, 1, ..., L und zugleich die Anzahl der Einsen die Werte (N-K), ..., N annehmen kann. Also muss der Hamming-Abstand der gesuchten Dualzahlen von (0, 0, ..., 0) zwischen N-K und L liegen. Die Anzahl dieser Dualzahlen berechnet sich mit Gleichung (8) in Abbildung 4.

Aufgabe: Für welchen Wert von N erhält man bei gegebenen K und L in Gleichung (8) in Abbildung 4 genau einen Summanden auf der rechten Seite?

Veranschaulichung des Abzählproblems im Pascalschen Dreieck

Die letzten Überlegungen wirken sehr abstrakt, lassen sich aber leicht veranschaulichen. Dazu werden in Abbildung 5 sämtliche Möglichkeiten aufgeführt, die es beim Ziehen mit Zurücklegen gibt, wenn man N = 5 wählt; es sind 2⁵ = 32 Möglichkeiten.

Sie werden aber in einer speziellen Weise angeordnet, nämlich gemäß der geometrischen Interpretation der Binomialkoeffizienten, die in Grundbegriffe der Wahrscheinlichkeitsrechnung: Binomialkoeffizienten, das Pascalsche Dreieck und der n-dimensionale Hyperwürfel entwickelt wurde: Die 32 Möglichkeiten können als Dualzahlen oder als Koordinaten der Eckpunkte eines fünfdimensionalen Hyperwürfels interpretiert werden. Geht man vom Ursprung aus, so beschreiben die Binomialkoeffizienten "k aus 5" jeweils die Anzahl der Eckpunkte in einem Hamming-Abstand k, wobei k = 0, 1, ..., 5. Als Dualzahlen interpretiert, handelt es sich um fünf-stellige Dualzahlen mit k Einsen und 5-k Nullen.

Abbildung 5: Dargestellt sind alle fünf-stelligen Dualzahlen; sie werden gemäß ihrem Hamming-Abstand k zu (0, 0, 0, 0, 0) in Gruppen der Größe "k aus 5" zusammengefasst. Dieser Hamming-Abstand kann die Werte k = 0, 1, ..., 5 annehmen. Die Anordnung erleichtert die Lösung des Abzählproblems beim Ziehen ohne Zurücklegen: Werden N = 5 Lose bei K = 3 und L = 2 gezogen, so sind nur die rot gekennzeichneten Dualzahlen mögliche Ergebnisse der Ziehungen. Beim Ziehen mit Zurücklegen beschreiben alle 32 Dualzahlen mögliche Ergebnisse.

Diese Anordnung erleichtert die Interpretation beim Ziehen von Losen aus einem Lostopf: Die 32 Möglichkeiten bestehen beim 5-maligen Ziehen mit Zurücklegen und die Anordnung von links nach rechts in Abbildung 5 entspricht der Anzahl der Nieten, die dabei gezogen wurden: k = 0, 1, ..., 5. Befinden sich im Lostopf K = 3 Nieten und L = 2 Treffer (wie im Beispiel in den Abbildungen 1 und 2) und wird 5-mal ohne Zurücklegen gezogen, so können nicht alle 32 Möglichkeiten eintreten, sondern nur die 10 Möglichkeiten zum Hamming-Abstand 2 vom Ursprung, die in Abbildung 5 rot gekennzeichnet sind.

Abbildung 6 zeigt die entsprechende Anordnung der 2⁴ = 16 Möglichkeiten, die bei N = 4 Ziehungen mit Zurücklegen eintreten können. Wird dagegen ohne Zurücklegen gezogen und befinden sich K = 3 Nieten und L = 2 Treffer im Lostopf, so sind wieder nur die rot gekennzeichneten Ergebnisse möglich. Diese Ergebnisse werden dadurch charakterisiert, dass ihr Hamming-Abstand zum Ursprung gleich 1 oder 2 ist (es können ein oder zwei Treffer enthalten sein).

Abbildung 6: Analog zu Abbildung 5 werden hier die möglichen Ergebnisse bei N = 4 Ziehungen dargestellt. Beim Ziehen mit Zurücklegen gibt es 16 Möglichkeiten; beim Ziehen ohne Zurücklegen für K = 3 und L = 2 nur die 10 rot gekennzeichneten Möglichkeiten.

Mit Hilfe der Abbildungen 5 und 6 kann man das oben gestellte Abzählproblem aus einer anderen Perspektive betrachten. Dazu soll Gleichung (2) in Abbildung 4 noch einmal hervorgehoben werden. Sie besagt, dass sich die Anzahl der N-stelligen Dualzahlen mit einem Hamming-Abstand k von (0, 0, ..., 0) durch den Binomialkoeffizienten "k aus N" berechnen lässt; dabei steht (0, 0, ..., 0) für den Nullvektor mit N Komponenten.

Man kann diese Gleichung aber auch anders interpretieren: Ist eine Dualzahl gegeben, so besitzt sie eine eindeutige Stellenzahl N und einen eindeutig definierten Hamming-Abstand k zu (0, 0, ..., 0). Und somit kann jeder Dualzahl eindeutig eine Position im Pascalschen Dreieck zugeordnet werden.

Mit dieser Interpretation von Gleichung (2) drängen sich folgende Fragen auf, die Gleichungen (4) und (5) in Abbildung 4 verallgemeinern:

Wo liegen im Pascalschen Dreieck diejenigen Dualzahlen (mit beliebiger Stellenzahl), die von (0, 0, ..., 0) einen Hamming-Abstand haben, der kleiner oder gleich einer gegebenen natürlichen Zahl L ist?
Wo befinden entsprechend Dualzahlen mit einem Hamming-Abstand von (0, 0, ..., 0), der zwischen den natürlichen Zahlen L₁ und L₂ liegt?

Sind diese Fragen beantwortet, so kann man wieder zur Ausgangsfrage dieses Kapitels zurückgehen, nämlich das oben gestellte Abzählproblem beim "Ziehen ohne Zurücklegen" zu lösen. Wenn man zu gegebener Nieten- und Treffer-Anzahl K und L die zugehörigen Dualzahlen im Pascalschen Dreieck identifizieren kann, so kann man sie leicht abzählen und hat eine "graphische" Lösung des Abzählproblems gefunden – so wie sie in Abbildung 3 mit dem gelben Rechteck gegeben wurde.

Dazu wird in Abbildung 7 das Pascalsche Dreieck gezeigt, wobei jeder Binomialkoeffizient durch eine Raute symbolisiert ist – die Position des Binomialkoeffizient "k aus N" lässt sich dann leicht durch Abzählen der Zeilen und Spalten bestimmen, wobei man beachten muss, dass an der Spitze des Pascalschen Dreiecks die Zeile zu N = 0 steht. Der Binomialkoeffizient "k aus N" beschreibt die Anzahl der N-stelligen Dualzahlen, die von (0, 0, ..., 0) einen Hamming-Abstand k besitzen.

Abbildung 7: Das Pascalsche Dreieck, in dem jeder Binomialkoeffizient durch eine Raute symbolisiert wird. Unten: Sucht man die Mächtigkeit der Menge der Dualzahlen, die eine Hamming-Abstand von (0, 0, ..., 0) haben, der kleiner oder gleich L ist, muss man die rot gekennzeichneten Binomialkoeffizienten summieren.

Um die Anzahl aller N-stelligen Dualzahlen zu bestimmen, die von (0, 0, ..., 0) einen Hamming-Abstand haben, der kleiner oder gleich L ist, muss man die Binomialkoeffizienten addieren, die in Abbildung 7 unten rot markiert sind.

Bisher wurde die Stellenzahl N der Dualzahlen fest vorgegeben; in Abbildung 2 wurde das Abzählproblem für alle N zwischen 1 und K + L = M gelöst. Daher wird man versuchen Abbildung 5 für beliebige N zu verallgemeinern.

In Abbildung 8 oben sind (grün) alle Binomialkoeffizienten eingetragen, die Dualzahlen beschreiben, die von (0, 0, ..., 0) einen Hamming-Abstand kleiner oder gleich L haben.

In der Mitte sind entsprechend die Binomialkoeffizienten eingetragen, so dass die zugehörigen Dualzahlen von (1, 1, ..., 1) einen Hamming-Abstand kleiner oder gleich K haben. Dies sind also Dualzahlen, die an K, K+1, ..., N Stellen eine 1 besitzen. Dies kann auch mit Nullen formuliert werden: Sie haben an 0, 1, ..., N-K Stellen eine 0.

Aber damit kann man diejenigen Dualzahlen charakterisieren, die für das Abzählproblem relevant sind: Dualzahlen mit höchstens L Einsen und höchstens K Nullen.

Abbildung 8: Veranschaulichung der Binomialkoeffizienten, die für das Abzählproblem relevant sind. Sucht man die Anzahl der N-stelligen Dualzahlen, die L Einsen und höchstens K Nullen haben, so muss man in der N-ten Zeile des Pascalschen Dreiecks diejenigen Binomialkoeffizienten addieren, die sich im gelben Rechteck befinden.

R-Skripte

Berechnung der Anzahl der Möglichkeiten beim Ziehen ohne Zurücklegen

Nachdem oben geklärt wurde, wie sich die Funktion A(K, L, N) als Summe von Binomialkoeffizienten berechnen lässt, ist ihre Implementierung nicht schwierig: In R steht mit der Funktion choose(n, k) die Berechnung der Binomialkoeffizienten zur Verfügung (ihre Dokumentation befindet sich im Paket base unter Special). Umständlich ist lediglich die Implementierung der Fallunterscheidung (siehe Abbildung 4).

Das folgenden Skript enthält einen Vorschlag für die Implementierung:

A <- function(K, L, N){
  stopifnot(N > 0, N <= K+L, K > 0 || L > 0)
  k.min <- min(K, L)
  k.max <- max(K, L)
  
  if(N <= k.min){
    return(2^N)
  } else {
    if(N <= k.max){
      return( sum(choose(n = N, k = 0:k.min)) )
    } else {
      return( sum(choose(n = N, k = (N - k.max):k.min)) )
    }
  }
}

Zur Erklärung:

Zeile 2: Prüfungen der Eingabewerte.

Zeile 3 und 4: Im Theorieteil oben wurde stets angenommen, dass K ≥ L; dies kann man bei der Implementierung nicht voraussetzen. Damit die folgende Fallunterscheidung einfacher wird, werden das Minimum und Maximum von K und L definiert und mit diesen weiter gerechnet.

Zeile 6 bis 14: Die Fallunterscheidung aus Abbildung 3. Ist N kleiner oder gleich dem Minimum von K und L (1. Fall in Abbildung 4), so kann A(K, L, N) allein aus N berechnet werden. Im zweiten und dritten Fall müssen Binomialkoeffizienten summiert werden (siehe Zeile 10 und 12).

Aufgabe: Überzeugen Sie sich davon, dass in Zeile 10 und 12 tatsächlich die Summe wie in den Gleichungen (7) und (8) in Abbildung 4 gebildet wird.

Beispiel für die Anwendung von A(K, L , N)

Die Anzahlen in Abbildung 2 kann man etwa durch das folgende Skript berechnen:

v <- sapply( X = (1:5), FUN = function(i){return( A(K = 3, L = 2, N = i) )} )
v
# [1]  2  4  7 10 10

Aufgabe: Testen Sie das Skript mit X = (0:5) beziehungsweise X = (1:6) .

Berechnung aller Möglichkeiten beim Ziehen ohne Zurücklegen

Nachdem die Funktion A(K, L, N) implementiert ist, sollen drei Algorithmen vorgestellt und diskutiert werden, die zu gegebenem K und L alle Möglichkeiten bei N Ziehungen berechnen; in Abbildung 2 wurden für K = 3, L = 2 und für N = 1, ..., 5 sämtliche möglichen Ergebnisse in den Tabellen gezeigt.

Die drei Algorithmen verwenden deutlich unterschiedliche Ansätze, die hier kurz beschrieben werden, die ausführliche Darstellung folgt in den jeweiligen Unterabschnitten. Gemeinsam ist den Algorithmen, dass sie die Ergebnisse wie Dualzahlen anzeigen und eine Matrix erzeugen, in der jede Spalte ein Ergebnis von N Ziehungen enthält – die Matrizen sind also (bis auf die Kopfzeilen) strukturiert wie die Tabellen in Abbildung 2.

Ein brute force-Algorithmus comb_wo_repl_bf() (combinations without replacement brute force), der zuerst alle 2^N Dualzahlen berechnet und anschließend feststellt, ob die Anzahl der Treffer und Nieten mit den gegebenen Zahlen L und K vereinbar ist. Falls nicht, wird das Ergebnis aus der Matrix gestrichen. Man erkennt sofort einen Nachteil: nach Abbildung 5 und 6 ist für N > L die Zahl 2^N meist deutlich größer ist als die Anzahl der möglichen Ergebnisse (rot gefärbten Spalten), wodurch der Algorithmus Speicherplatz verschwendet.
Zurückführung auf die Funktion combn() comb_wo_repl() : Die gesuchten Dualzahlen können durch die Anzahl an Nullen (beziehungsweise Einsen) eindeutig charakterisiert werden. Die Berechnung aller möglichen Dualzahlen mit gegebener Anzahl an Nullen und Einsen kann in R leicht mit Hilfe der Funktion combn() realisiert werden. Der zweite Algorithmus verfolgt diesen Ansatz.
Der dritte Algorithmus comb_wo_repl_rec() (combinations without replacement recursive) verwendet eine Rekursion. Denn das N-malige Ziehen ohne Zurücklegen kann in zwei Vorgänge zerlegt werden: Zuerst zieht man einmal, stellt das Ergebnis fest und bestimmt daraus, wie der Lostopf jetzt bestückt sein muss. Dann erfolgen die weiteren N - 1 Ziehungen unter den neuen Bedingungen. Da der zweite Teilvorgang bis auf die Parameter K, L und N mit dem Gesamtvorgang identisch ist, kann man eine Rekursion einsetzen.

Schon aus dieser groben Beschreibung kann man ablesen:

Der brute force-Algorithmus verwendet kaum theoretische Kenntnisse über das Ziehen ohne Zurücklegen. Die Implementierung wirkt nach obiger Beschreibung sehr einfach.
Der zweite Algorithmus setzt mehr Wissen über das Ziehen ohne Zurücklegen ein, überträgt den Großteil der Arbeit aber an die Funktion combn(). Wenn diese nicht zur Verfügung steht, muss man hier sehr viel mehr Arbeit leisten.
Die Implementierung der Rekursion erscheint im Vergleich zu den anderen Algorithmen als die schwierigste, insbesondere die Abbruchbedingungen sind sehr fehleranfällig. Wie bei der Rekursion geht aber kein Wissen über die Lösung des Abzählproblems in die Implementierung ein.

Berechnung mit brute force-Algorithmus

In diesem Unterabschnitt wird eine Funktion comb_wo_repl_bf(K = 2, L = 2, N = K+L) entwickelt, die zuerst alle möglichen Dualzahlen der Länge N erzeugt und anschließend alle streicht, die nicht mit der Anzahl K an Nullen und L an Einsen vereinbar sind. Eingabewerte sind die drei ganzen Zahlen K, L und N.

Die Vorgehensweise des brute force-Algorithmus kann man grob in drei Schritte einteilen:

Es wird eine Matrix m erzeugt, die alle 2^N Dualzahlen spaltenweise anordnet.
Mit Hilfe einer Funktion cnt() werden die Spalten von m untersucht.
In der Matrix m verbleiben nur diejenigen Spalten, die als Ergebnisse von N Ziehungen aus einem Lostopf mit K Nieten und L Treffern in Frage kommen.

Der Rückgabewert der Funktion comb_wo_repl_bf(K = 2, L = 2, N = K+L) ist dann die zuletzt beschriebene Matrix.

Die Hilfsfunktion cnt(v, max.0, max.1) erhält drei Eingabewerte:

Einen Vektor v, der die zu untersuchende Dualzahl enthält.
Die Anzahl der Nullen max.0, die in v maximal enthalten sein dürfen.
Die Anzahl der Einsen max.1, die in v maximal enthalten sein dürfen.

Rückgabewert ist der logische Wert, der das Ergebnis der Prüfungen angibt.

cnt <- function(v, max.0, max.1){
  result <- TRUE
  num.1 <- sum(v)
  num.0 <- length(v) - num.1
  if(max.0 < num.0 || max.1 < num.1){
    result <- FALSE
  }
  return(result)
}

Eine Prüfung der Eingabewerte wird nicht vorgenommen; man geht also davon aus, dass v tatsächlich eine Dualzahl beschreibt und dass max.0, max.1 natürliche Zahlen sind (einschließlich 0).

Zur Erklärung:

Zeile 3 und 4: Wenn v tatsächlich eine Dualzahl ist, kann man die Anzahl der enthaltenen Nullen und Einsen über die Summe der Komponenten und der Länge von v feststellen.

Zeile 5 bis 8: Falls mehr als max.0 Nullen beziehungsweise max.1 Einsen in v enthalten sind, wird FALSE zurückgegeben, andernfalls TRUE.

Die Funktion comb_wo_repl_bf(K = 2, L = 2, N = K+L) erhält als Eingabewerte K, L, und N, für die einfache default-Werte gesetzt sind (Zeile 1). In den Zeilen 2 und 3 wird die Matrix m vorbereitet, die zunächst alle 2^N Dualzahlen enthält (Zeile 6 bis 15). Zum Erzeugen der Dualzahlen wird die Funktion rep() eingesetzt, die die Regelmäßigkeiten der Folge der Nullen und Einsen ausnützt, wenn man die Dualzahlen lexikographisch anordnet.

Die Spalten von m werden untersucht (Zeile 20), in dem man in der Funktion apply() die Hilfsfunktion cnt() aufruft und für sie die Argumente max.0 = K, max.1 = L setzt. Der von apply() berechnete Vektor idx ist eigentlich ein logischer Vektor. Er wird verwendet (Zeile 21), um aus der Matrix die geeigneten Spalten herauszufiltern.

comb_wo_repl_bf <- function(K = 2, L = 2, N = K+L){
  cls <- 2^N
  m <- matrix(data = 0, nrow = N, ncol = cls)
  
  # Matrix mit allen Dualzahlen füllen
  eac <- cls / 2
  tim <- 1
  v0 <- c(0, 1)
  
  for(i in (1:N)){
    v <- rep(v0, each = eac, times = tim)
    m[i, ] <- v
    eac <- eac / 2
    tim <- 2 * tim
  }  
  
  # Matrix m untersuchen: erlaubt in jeder Spalte:
  # maximal K Nullen, L Einsen, andere nicht erlaubt
  
  idx <- apply(X = m, MARGIN = 2, FUN = cnt, max.0 = K, max.1 = L)
  return(m[, idx])
}

Aufgabe:

Schreiben Sie alle dreistelligen Dualzahlen in lexikographischer Anordnung auf und zwar so, wie sie in der Matrix m angeordnet werden.

Beschreiben Sie, welche Regelmäßigkeiten die Folgen von Nullen und Einsen haben, wenn man die Matrix zeilenweise liest.

Überprüfen Sie für N = 3, ob mit den Anweisungen in Zeile 6 bis 15 tatsächlich alle dreistelligen Dualzahlen in lexikographischer Anordnung erzeugt werden.

♦ ♦ ♦

Der Nachteil dieses brute force-Algorithmus ist offensichtlich: Es wird eine Matrix mit 2^N Spalten erzeugt, von denen ein Großteil wieder gestrichen wird, da A(K, L, N) für N > L kleiner ist als 2^N. Für große N kann es leicht passieren, dass sich die Matrix nicht mehr erzeugen lässt oder unzumutbar viel Speicherplatz benötigt wird. Der folgende grob beschrieben brute force-Algorithmus vermeidet diesen Nachteil und verwendet ebenso wenige Kenntnisse über das Ziehen ohne Zurücklegen:

Man benötigt einen Zähler, der zu gegebenem N alle Dualzahlen von 0 bis 2^N - 1 erzeugt, wobei die Dualzahlen als Vektoren vorliegen.
Es wird eine "leere Matrix" vorbereitet (in R geschieht dies durch m <- c() ).
In einer Schleife werden die Dualzahlen von 0 bis 2^N - 1 erzeugt.
Für jede Dualzahl (Vektor v) wird – wie oben mit Hilfe der Funktion cnt() – festgestellt, ob die Anzahl der Nullen und Einsen mit der vorgegebenen Anzahl an Nieten K und Treffern L vereinbar ist. Falls ja, wird die Dualzahl an die Matrix m angehängt (in R mit m <- cbind(m, v) ).
Nach Beendigung der Schleife enthält die Matrix m alle gesuchten Möglichkeiten und wird zurückgegeben.

Aufgabe: Implementieren Sie den zuletzt beschriebenen brute force-Algorithmus und beurteilen Sie, ob er die Nachteile des ersten brute force-Algorithmus vermeidet oder andere besitzt.

Hinweis: In Stellenwertsysteme und Umrechnung zwischen den wichtigsten Zahlensystemen: Dezimalsystem, Hexadezimalsystem, Dualsystem wurde ein Zähler implementiert, der sogar in einem beliebigen Zahlensystem zählt. Für das Dualsystem lässt sich dortige Zähler sicher vereinfachen.

Berechnung mit Hilfe von combn()

Der zweite Algorithmus ist sehr schlank, da er geschickt die Funktion combn() (aus dem Basis-Paket utils) einsetzt, die den Großteil der Arbeit übernimmt. Um den Algorithmus besser zu verstehen soll an einem einfachen Beispiel die Arbeitsweise von combn() gezeigt werden; nach den Untersuchungen zum Ziehen ohne Zurücklegen ist es nicht mehr schwer, daraus den gewünschten Algorithmus zu implementieren. Ausführlicher erklärt wird die Funktion combn() in den R-Skripten in Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik.

Im folgenden Beispiel werden alle zwei-elementigen Teilmengen der Menge {1, 2, 3, 4, 5} berechnet. Dazu wird combn() mit x = 5 und m = 2 aufgerufen. Für x wird üblicherweise ein Vektor eingegeben, der die Menge repräsentiert, aus der die Elemente ausgewählt werden sollen. Gibt man für x eine natürliche Zahl n ein, wird die Menge x = {1, ..., n} verwendet. Das Argument m gibt an, wie viele Elemente ausgewählt werden sollen.

combn(x = 5, m = 2)
#       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,]    1    1    1    1    2    2    2    3    3     4
# [2,]    2    3    4    5    3    4    5    4    5     5

Die berechneten Teilmengen werden als Spalten-Vektoren zu einer Matrix zusammengefasst und zurückgegeben. Somit ist die Zeilenanzahl gleich 2 und die Spaltenanzahl gleich der Anzahl der zwei-elementigen Teilmengen von {1, 2, 3, 4, 5}; dies berechnet sich durch den Binomialkoeffizienten "2 aus 5" = 10.

Die Funktion combn() kann noch weiter konfiguriert werden; hier wird verwendet, dass man als Argument FUN eine Funktion angeben kann, die auf die Spalten-Vektoren angewendet wird; erst anschließend werden die Ergebnisse dieser Berechnung zu einem neuen Objekt zusammengefügt, das jetzt keine Matrix mehr sein muss.

Man kann ganz einfach einen Zusammenhang zwischen den Teilmengen einer N-elementigen Menge und den N-stelligen Dualzahlen herstellen. Für das Beispiel oben mit N = 5 lautet er: Interpretiert man die Zahlen 1, ..., 5 der Menge x als Indizes einer fünf-stelligen Dualzahl, so geben die Teilmengen an, an welcher Stelle in der Dualzahl eine 1 steht. Um die von combn() berechneten Teilmengen in Dualzahlen umzurechnen, muss man somit nur eine geeignete Funktion implementieren. Unten wird diese Funktion als anonyme Funktion implementiert: FUN = function(idx){v <- rep(x = 0, times = N); v[idx] <- 1; return(v)} .

Dabei ist idx je eine Teilmenge, die von combn() erzeugt wurde (im Beispiel des letzten Listings die Spalten der Matrix). Man bildet zuerst einen Vektor der Länge N, der nur aus Nullen besteht. Die in idx ausgewählten Zahlen werden als Index des Vektors v interpretiert und verwendet, um die entsprechenden Komponenten gleich 1 zu setzen. Somit entsteht eine Dualzahl (als Vektor der Länge N).

Jetzt muss man nur noch dafür sorgen, dass combn() mit den richtigen Werten des Argumentes m aufgerufen wird.

Das folgende Listing zeigt eine Implementierung, die zum Teil die Vorgehensweise zur Berechnung von A(K, L, N) übernimmt:

Für die Eingabewerte K, L, und N werden einfache default-Werte gesetzt (Zeile 1).
Prüfungen der Eingabewerte in Zeile 2.
Minimum und Maximum von K und L werden definiert (Zeile 4 und 5).
Da an die zu erzeugende Matrix fortlaufend Spalten hinzugefügt werden, startet man mit der "leeren Matrix" m <- c() (Zeile 8).
In der Fallunterscheidung wird festgelegt, zu welchen Hamming-Abständen von (0, 0, ..., 0) die Dualzahlen berechnet werden müssen; die Fallunterscheidung wurde ähnlich bei A(K, L, N) eingesetzt.
In der for-Schleife (Zeile 24 bis 27) wird dann über die zuletzt festgelegten Hamming-Abstände iteriert. Das Herzstück des Algorithmus ist dann die Umrechnung der von combn() gebildeten Teilmenge von {1, ..., N} in eine Dualzahl in Zeile 25. Jede der dabei erzeugten Matrizen m.i wird dann spaltenweise zur schon bestehenden Matrix hinzugefügt.
Zuletzt wird die Matrix m zurückgegeben (Zeile 29).

comb_wo_repl <- function(K = 2, L = 2, N = K+L){
  stopifnot(N > 0, N <= K+L, K > 0 || L > 0)

  k.min <- min(K, L)
  k.max <- max(K, L)
  
  # Matrix vorbereiten:
  m <- c()
  
  # Fallunterscheidung und Schleife über i
  # i: entspricht einem Hamming-Abstand: 
  # es werden alle Dualzahlen mit d_H = i zu (0, ..., 0) erzeugt
    
    if(N <= k.min){    # 1. Fall: N <= k.min
      ks <- (0:N)
    } else {
      if(N <= k.max){    # 2. Fall: k.max < N <= k.max
        ks <- (0:k.min)
      } else {    # 3. Fall: N > k.max
        ks <- ((N-k.max):k.min)
      }
    }
    
  for(i in ks){
    m.i <- combn(x = N, m = i, FUN = function(idx){v <- rep(x = 0, times = N); v[idx] <- 1; return(v)})
    m <- cbind(m, m.i)
  }

  return(m)
}

Als Beispiel für die Anwendung von comb_wo_repl() werden wieder die Tabellen aus Abbildung 2 berechnet:

for(i in (1:5)){
  cat("i = ", i, "\n")
  print( comb_wo_repl(K = 3, L = 2, N = i) )
  cat("\n")
}
# i =  1 
#      m.i m.i
# [1,]   0   1
# 
# i =  2 
#      [,1] [,2] [,3] [,4]
# [1,]    0    1    0    1
# [2,]    0    0    1    1
# 
# i =  3 
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
# [1,]    0    1    0    0    1    1    0
# [2,]    0    0    1    0    1    0    1
# [3,]    0    0    0    1    0    1    1
# 
# i =  4 
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,]    1    0    0    0    1    1    1    0    0     0
# [2,]    0    1    0    0    1    0    0    1    1     0
# [3,]    0    0    1    0    0    1    0    1    0     1
# [4,]    0    0    0    1    0    0    1    0    1     1
# 
# i =  5 
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,]    1    1    1    1    0    0    0    0    0     0
# [2,]    1    0    0    0    1    1    1    0    0     0
# [3,]    0    1    0    0    1    0    0    1    1     0
# [4,]    0    0    1    0    0    1    0    1    0     1
# [5,]    0    0    0    1    0    0    1    0    1     1

Berechnung mit Rekursion

Die Vorgehensweise bei der rekursiven Berechnung aller möglichen Ergebnisse beim Ziehen ohne Zurücklegen kann man leicht an der Tabelle in Abbildung 1 unten veranschaulichen. Dazu wird die Tabelle in zwei Teile zerlegt:

Die erste Zeile mit den Ergebnissen der ersten Ziehung: Niete (0) und Treffer (1) kommen mit einer Häufigkeit vor, die mit der Funktion A() berechnet werden kann – Genaueres wird sofort beschrieben.
Die Matrizen unterhalb der Nieten beziehungsweise Treffer, die wiederum alle möglichen Ergebnisse beim Ziehen ohne Zurücklegen beschreiben – aber jetzt mit anderen Parametern K, L und N.

Sollen für einen Lostopf mit K Nieten und L Treffern alle möglichen Ergebnisse bei N Ziehungen ohne Zurücklegen berechnet werden, dann gilt:

Wird im ersten Zug eine Niete gezogen, dann befinden sich noch K-1 Nieten und L Treffer im Lostopf, aus dem noch weitere N-1 Lose gezogen werden. Die Anzahl der Ergebnisse der N-1 weiteren Ziehungen beträgt also A(K-1, L, N-1).
Wird ein Treffer gezogen, dann befinden sich noch K Nieten und L-1 Treffer im Lostopf, aus dem noch weitere N-1 Lose gezogen werden. Die Anzahl der Ergebnisse der N-1 weiteren Ziehungen beträgt also A(K, L-1, N-1).

Diese Rekursion ist – wie meistens bei Rekursionen – einfach zu formulieren, fehleranfällig ist dagegen die Festlegung der Abbruchbedingungen: In welchen Fällen muss die Rekursion abgebrochen werden und wie lauten dann die "zwei Teile", also erste Zeile der Tabelle und die Matrizen unter den Nullen beziehungsweise Einsen?

Um nicht auszuschweifen, wird sofort der Quelltext der Funktion comb_wo_repl_rec(K = 2, L = 2, N = K+L) gezeigt und die kritischen Stellen anschließend erläutert. Wie bei den anderen Algorithmen werden die möglichen Ergebnisse der Ziehungen als Spalten-Vektoren zu einer Matrix zusammengefasst und zurückgegeben.

comb_wo_repl_rec <- function(K = 2, L = 2, N = K+L){
  stopifnot(N > 0, N <= K + L)
  
  # 4 Abbruchbedingungen:
  if(identical(N, 1) && K > 0 && L > 0){
    return( matrix(data = c(0, 1), nrow = 1, ncol = 2, byrow = TRUE) )
  }
  
  if(identical(K, 0) && identical(L, 0)) return(NULL)
  
  if(identical(K, 0)){
    return( matrix(data = 1, nrow = N, ncol = 1, byrow = TRUE) )
  }
  
  if(identical(L, 0)){
    return( matrix(data = 0, nrow = N, ncol = 1, byrow = TRUE) )
  }
  
  # Wiederholungen der 0:
  v0 <- rep( x = 0, times = A(K = K-1, L = L, N = N-1) )
  # Wiederholungen der 1:
  v1 <- rep( x = 1, times = A(K = K, L = L-1, N = N-1) )
  
  # rbind() v0 und Matrix unter v0:
  m0 <- rbind( v0, comb_wo_repl_rec(K = K-1, L = L, N = N - 1) )
  dimnames(m0) <- NULL
  # rbind() v1 und Matrix unter v1:
  m1 <- rbind( v1, comb_wo_repl_rec(K = K, L = L-1, N = N - 1) )
  dimnames(m1) <- NULL

  return(cbind(m0, m1))
}

Zur Erklärung:

Zeile 2: Für N = 0 oder N ≥ K + L wird die Funktion nicht ausgeführt, sondern eine Fehlermeldung ausgegeben. In den Abbruchbedingungen der Rekursion müssen daher diese beiden Fälle nicht berücksichtigt werden.

Zeile 5 bis 17: Es werden insgesamt 4 Abbruchbedingungen formuliert; ohne den stopifnot()-Befehl in Zeile 2 müsste man hier weitere Bedingungen aufnehmen.

Zeile 5 bis 7: Wegen des stopifnot()-Befehls in Zeile 2 kann N nur die relevanten Werte 1, ..., K+L annehmen. Falls N = 1 wird nur noch ein Los gezogen. Und falls noch beide Arten von Losen im Lostopf sind (K > 0 && L > 0 ), kann im letzten Zug entweder 0 oder 1 gezogen werden. Die zu bildende Matrix besteht also nur aus einer Zeile mit diesen beiden Möglichkeiten (Zeile 6). Dass im Lostopf nur noch Nieten oder nur noch Treffer enthalten sind, wird in der dritten und vierten Abbruchbedingung abgearbeitet.

Zeile 9: Falls kein Los im Lostopf enthalten ist, kann keine Matrix mit möglichen Ergebnissen gebildet werden und es wird NULL zurückgegeben.

Zeile 11 bis 13: Falls keine Niete im Lostopf enthalten ist, können nur noch Treffer gezogen werden (dass keine Treffer mehr enthalten sind, kann wegen Zeile 9 nicht mehr eintreten). Wegen stopifnot(N > 0, N <= K + L) werden tatsächlich die verbleibenden N Ziehungen ausgeführt. Die zu bildende Matrix enthält eine Spalte mit N Einsen.

Zeile 15 bis 17: Analog der Fall, dass die Urne keine Treffer enthält.

Damit sind die Sonderfälle der Abbruchbedingungen abgearbeitet, der folgende Quelltext beschreibt den Fall, dass tatsächlich eine erste Zeile und Matrizen darunter gebildet werden müssen, wobei das Erzeugen dieser Matrizen durch den rekursiven Aufruf von comb_wo_repl_rec() erfolgt.

Zeile 19 bis 31: Umsetzung der oben grob beschriebenen Rekursion. Es wird die erste Zeile gebildet (die wiederum aus einer gewissen Anzahl von Nullen und Einsen besteht) sowie die Matrizen m0 und m1 unter den Nullen beziehungsweise Einsen. Die Matrizen m0 und m1 werden nicht explizit berechnet, sondern durch den rekursiven Aufruf von comb_wo_repl_rec() erzeugt.

Zeile 20 und 22: Mit Hilfe der Funktion A() wird berechnet, wie oft Nullen beziehungsweise Einsen im nächsten Zug (also der ersten Zeile der Matrix) auftreten können. Mit diesen Anzahlen werden mit der Funktion rep() die Wiederholungen der 0 beziehungsweise der 1 als Vektoren v0 und v1 gebildet.

Zeile 25 und 26: Die Matrix unterhalb v0 wird durch den rekursiven Aufruf von comb_wo_repl_rec() erzeugt; der Vektor v0 und diese Matrix werden mit rbind() zu m0 zusammengefügt. Da bei der Verwendung von rbind() irreführende dimnames gesetzt werden, werden sie wieder entfernt.

Zeile 28 und 29: Analog bestimmt man den Vektor v1 der Einsen und die Matrix m1.

Zeile 31: Mit Hilfe von cbind() werden die Matrizen m0 und m1 spaltenweise zusammengefügt und dann zurückgegeben.

Beurteilung der drei Algorithmen

1. Speicherplatz und Rechenzeit:

Oben wurde bereits darauf hingewiesen, dass der brute force-Algorithmus einen sehr hohen Speicherbedarf hat, da zuerst alle 2^N Dualzahlen berechnet werden (als Spalten einer Matrix) und anschließend diejenigen Dualzahlen entfernt werden, die nicht mit den gegebenen Nieten- und Treffer-Anzahlen K und L verträglich sind. Verwendet man den (in der Aufgabe angedeuteten) Zähler für Dualzahlen, kann man zwar den Speicherplatz auf die Größenordnung des tatsächlich benötigten Bereiches beschränken, stattdessen wird die Rechenzeit stark anwachsen, da das Abzählen der Dualzahlen mit sehr vielen Funktionsaufrufen verbunden ist.

Die anderen beiden Algorithmen haben den Vorteil, dass auch nur Speicherplatz in der Größenordnung belegt wird, wie er für die Berechnung des Rückgabewertes nötig ist. Bei der Zuhilfenahme von combn() ist schwer durchschaubar, wie die Rechenzeit mit N anwächst; da combn() und die Umrechnung einer Teilmenge in eine Dualzahl nahezu alle Aufgaben erledigen, ist die Rechenzeit vor allem davon abhängig, wie schnell die Funktion combn() ist. Die Rekursion hat ebenfalls den Nachteil, dass sie zahlreiche Funktionsaufrufe erfordert; auch bei ihr wird die Rechenzeit sehr schnell mit N anwachsen.

Die Verwendung der Lösung des Abzählproblems:

Ein anderer Aspekt soll hier betont werden, da er für die Implementierung von Lösungen zu Abzählproblemen von allgemeiner Bedeutung ist: welches Wissen über die Lösung des Abzählproblems geht in die Implementierung ein?

Wenn hier von einer "Lösung eines Abzählproblems" die Rede ist, sind eigentlich zwei unterschiedliche Probleme gemeint – was unten dazu gesagt wird betrifft beide Probleme:

Die Berechnung der Anzahl der Möglichkeiten, in diesem Fall die Funktion A(K, L, N).
Die Berechnung aller möglichen Ergebnisse, hier die Matrizen, die von den drei Algorithmen erzeugt werden.

Bei der Lösung von Abzählproblemen steht man oft vor folgendem Aufgabe: Man möchte es mit gegebenen Parametern (hier K, L und N) durch ein Programm lösen lassen, kennt aber die theoretische Lösung des Problems nicht. Dann benötigt man einen Algorithmus, der tatsächlich nur die Problemstellung umsetzt, aber nicht die theoretische Lösung verwendet.

Der oben gezeigte brute force-Algorithmus ist ein Paradebeispiel für diesen Fall: Man erzeugt zunächst eine Menge von Ergebnissen, die mit Sicherheit alle gesuchten Ergebnisse umfasst und entscheidet dann, welche dieser Ergebnisse tatsächlich das Abzählproblem lösen. Zur Implementierung muss man dann nur die Problemstellung verstanden haben und richtig umsetzen. Dabei entstehen oft Algorithmen, die sich sehr leicht implementieren lassen, die aber einen hohen Speicherbedarf oder lange Rechenzeiten haben. Aber wenn man die theoretische Lösung nicht kennt, wird man diese Nachteile in Kauf nehmen.

Dagegen könnte der Algorithmus, der auf combn() zurückgreift, nicht ohne die explizite Lösung des Abzählproblems implementiert werden.

Bei der rekursiven Berechnung der möglichen Ergebnisse muss man unterscheiden:

Der Algorithmus verwendet die Funktion A(K, L, N), beruht somit auf der theoretischen Lösung des Abzählproblems.
Weiter geht kein spezifisches Wissen über das Abzählproblem ein. Die Lösung ist typisch für eine Rekursion: das Problem wird in zwei Teile zerlegt (Ausführen einer Ziehung, Ausführen von N-1 Ziehungen), wobei das zweite Problem strukturgleich zum Gesamtproblem ist, so dass man es rekursiv formulieren kann.

Wenn man daher auch das Abzählen der möglichen Ergebnisse durch eine Rekursion erledigt (siehe Aufgabe weiter unten), hat man wiederum einen Algorithmus formuliert, der keine Kenntnis der theoretischen Lösung voraussetzt.

In den Artikeln Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars, Spezielle Abzählprobleme: Partitionen und Lösung von Abzählproblemen durch Rekursion wird der Ansatz der Rekursion verwendet, um alle Kombinationen mit Wiederholungen und alle Partitionen zu berechnen. Diese Beispiele sollen dann verdeutlichen, wie wichtig derartige Lösungen sein können für Abzählprobleme, die man nicht (oder nur sehr schwer) explizit lösen kann.

Aufgaben

1. Zusätzliche Funktionalität: "Ziehen mit Zurücklegen"

Die oben vorgestellten Algorithmen können leicht so umgeschrieben werden, dass sie sowohl für das Ziehen mit Zurücklegen als auch das Ziehen ohne Zurücklegen alle möglichen Ergebnisse berechnen. Sie benötigen dann ein weiteres Argument, etwa replace = TRUE ; im default-Fall müssen dann die Argumente K und L nicht gesetzt werden. Für replace = FALSE können die bereits implementierten Funktionen aufgerufen werden.

Implementieren Sie die drei Algorithmen zum Ziehen mit Zurücklegen nach dem Muster der drei Algorithmen oben und bilden Sie damit Funktionen

combinations_bf(K = 2, L = 2, N = K+L, replace = TRUE) ,
combinations(K = 2, L = 2, N = K+L, replace = TRUE) ,
combinations_rec(K = 2, L = 2, N = K+L, replace = TRUE) .

2. Berechnung von A(K, L, N) mit Hilfe einer Rekursion

So wie die Funktion A(K, L, N) oben implementiert wurde, muss die Lösung des Abzählproblems bekannt sein, also die Gleichungen (6-8) in Abbildung 4. Implementieren Sie eine Rekursion zur Berechnung von A(K, L, N), die nicht auf die Lösung des Abzählproblems zurückgreift (also ähnlich arbeitet wie die rekursive Berechnung aller Möglichkeiten beim Ziehen ohne Zurücklegen).