Spezielle Abzählprobleme: Partitionen

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Wahrscheinlichkeitsrechnung
    • Grundbegriffe der Wahrscheinlichkeitsrechnung
      • Grundbegriffe der Wahrscheinlichkeitsrechnung: einfache Abzählprobleme
      • Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik
      • Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars

Einführung

Zur Erinnerung: Kombinationen mit Wiederholungen

In Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars wurde ausführlich das folgende Abzählproblem behandelt, das dort meist mit "Lotto K aus N mit Wiederholungen" bezeichnet wurde:

In einer Urne befinden sich N unterscheidbare Kugeln (etwa durchnumeriert vo 1 bis N), von denen K gezogen werden und zwar mit Zurücklegen (das heißt jede gezogene Kugel wird sofort wieder in die Urne zurückgelegt und kann auch im nächsten Zug gezogen werden). Die Ergebnisse werden anschließend sortiert (meist aufsteigend). Gefragt ist nach der Anzahl der möglichen Ergebnisse.

Im zitierten Kapitel wurde auch gezeigt, dass das soeben geschilderte Abzählproblem zu folgendem Abzählproblem äquivalent ist: Eine ganze Zahl K soll als Summe von N Summanden dargestellt werden, wobei gelten soll:

• Die Null ist als Summand zugelassen.
• Wird die Reihenfolge der Summanden vertauscht, so zählt dies als neue Lösung.

Man nennt N Summanden, die sich zu K addieren, eine geordnete Partition von K der Länge N (geordnet soll heißen, dass auf die Anordnung der Summanden geachtet wird).

Als Abzählproblem formuliert: Wie viele unterschiedliche geordnete Partitionen der Zahl K der Länge N gibt es?

Als Beispiel wird K = 4 und N = 2 gewählt. Beachtet man obige Vorgaben, so gibt es 5 unterschiedliche Partitionen:

4 + 0 = 4
3 + 1 = 4
2 + 2 = 4
1 + 3 = 4
0 + 4 = 4

Die Anzahl der Partitionen kann mit Hilfe des Binomialkoeffizienten "K aus N-1+K" berechnet werden, was im Beispiel auf "4 aus 5" führt.

Die hier behandelten Abzählprobleme

Betrachtet man oben die Formulierung des Abzählproblems mit Hilfe von Partitionen, so ist es naheliegend folgende Abzählprobleme zu behandeln:

1. Wie viele ungeordnete Partitionen einer Zahl K der Länge N gibt es? Hier wird die Null weiterhin als Summand zugelassen.
2. Wie viele ungeordnete Partitionen einer Zahl K der Länge N gibt es, wenn die Null nicht als Summand zugelassen ist?

Mit ungeordneter Partition ist jetzt gemeint, dass die Partitionen, die nur durch Vertauschung der Summanden auseinander hervorgehen, nicht als neue Lösung zählen. Man muss jetzt nur noch vereinbaren, ob die Summanden auf- oder absteigend angegeben werden.

Im ersten Fall lauten die drei ungeordneten Partitionen von K = 4 der Länge N = 2 (mit aufsteigenden Summanden):

0 + 4 = 4
1 + 3 = 4
2 + 2 = 4

Im zweiten Fall gibt es nur noch zwei Partitionen:

1 + 3 = 4
2 + 2 = 4

Die Methoden, mit denen hier die Abzählprobleme untersucht werden, sind sehr ähnlich wie in Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars. Die Ergebnisse sind aber eher enttäuschend: Obwohl die Abzählprobleme so eng verwandt mit den geordneten Partitionen erscheinen, ist es nicht möglich, eine einfache Formel herzuleiten, mit der sich die Anzahl der möglichen Partitionen berechnen lässt. Es werden lediglich Rekursionsformeln hergeleitet, die dann numerisch ausgewertet werden können.

Es wird nicht versucht mehrere äquivalente Abzählprobleme zu den untersuchten Problemen zu finden. Wie man dabei vorgeht, wurde bei den Kombinationen mit Wiederholungen ausführlich beschrieben und soll hier nicht wiederholt werden. Es wird lediglich die Verbindung zur Aufteilung von Kugeln auf Urnen hergestellt.

Bezeichnungen

Um eine suggestivere Symbolik für die zu zerlegende Zahl und die Anzahl ihrer Teile (Summanden) wird nicht mehr die Bezeichnung aus Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars verwendet, sondern folgende Konvention eingeführt:

1. Die Zahl wird stets mit Z bezeichnet, sie kann nur positive Werte annehmen.
2. Die Länge der Partition wird mit L bezeichnet.
3. Die Teile (oder Summanden) der Partition werden mit z₁, ..., z_L bezeichnet, also

Z = z₁ + ... + z_L.

Die Summanden werden meist in aufsteigender Reihenfolge angegeben.

Um sich wiederholende Satzungetüme wie "die Menge der ungeordneten Partition von Z der Länge L, wobei die Null als Summand zugelassen ist," zu vermeiden, wird immer dann, wenn aus dem Zusammenhang klar ist, welches Problem gerade diskutiert wird, einfach von der "Menge aller Partitionen" oder der "Anzahl aller Partitionen" gesprochen.

Ungeordnete Partitionen, bei denen 0 als Summand nicht erlaubt ist

Die Problemstellung

Es sollen Z nicht unterscheidbare Kugeln auf L Urnen verteilt werden, die ebenfalls nicht unterscheidbar sind. Keine der Urnen darf leer bleiben, also muss Z ≥ L sein.

Jede Realisierung des Experiments kann durch eine Folge von echt positiven Zahlen, den Besetzungszahlen,

z₁, z₂, ..., z_L mit z₁ + z₂ + ... + z_L = Z

beschrieben werden.

Die Angabe der Zahlen z₁, ₂, ..., z_L suggeriert allerdings, dass hier eine Zuordnung vorgenommen wird, nämlich dass der Index die Urne angibt, in der sch die zugehörige Anzahl von Kugeln befindet. Diese Zuordnung soll hier nicht mehr möglich sein, da die Urnen nicht unterscheidbar sind (also nicht numeriert).

Die Besetzungszahlen werden aufsteigend sortiert, also

z₁ ≤ z₂ ≤ ... ≤ z_L.

Gesucht ist die Anzahl der möglichen Realisierungen.

Formuliert man das Problem ohne die Veranschaulichung mit Kugeln und Urnen, so lautet es:

Zu gegebenen ganzen Zahlen Z und L ist die Anzahl der aufsteigenden Folgen nicht-negativer Zahlen gesucht; dabei haben die Folgen die Länge L und die Folgenglieder addieren sich zu Z:

0 < z₁ ≤ z₂ ≤ ... ≤ z_L und z₁ + z₂ + ... + z_L = Z.

Oder kurz:

Gesucht ist die Anzahl der ungeordneten Partitionen von Z der Länge L, wobei kein Summand gleich null sein darf.

Die folgende Tabelle zeigt die Lösungen des Problems für Z = 12 und L = 4 (die erste Zeile dient der Numerierung der Partitionen):

Tabelle 1: Die 15 Partitionen von Z = 12 der Länge L = 4.

Herleitung einer Rekursionsformel

Die Anzahl der Partitionen einer Zahl Z der Länge L wird im Folgenden mit

p(Z, L)

bezeichnet. (Natürlich mit den Voraussetzungen, dass vertauschte Reihenfolgen der Summanden nicht gezählt werden und dass kein Summand gleich 0 sein darf.)

Um für p(Z, L) eine Rekursionsformel herzuleiten, muss man versuchen, in Tabelle 1 eine gewisse Regelmäßigkeit zu erkennen. Zunächst sollte auffallen, dass man die Tabelle in zwei Teile zerlegen kann:

1. Es gibt Partitionen, die mit 1 beginnen (im Beispiel sind es die ersten 10).
2. Die anderen 5 Partitionen enthalten keine 1 (da die Summanden aufsteigend dargestellt werden, kann eine Partition, die an der ersten Stelle keine 1 hat, nirgends eine 1 haben).

Betrachtet man diese beiden Teile genauer, fällt auf:

1. Wenn der erste Summand z₁ = 1 ist, muss die Summe der anderen drei Summanden z₂ + z₃ + z₄ = 9 ergeben. Und die 10 Partitionen der 9 sind zugleich alle Partitionen der 9. Denn: Gäbe es eine weitere Partition der 9, hätte man zugleich eine weitere Partition der 10 gefunden (indem man wieder z₁ = 1 setzt); es war aber vorausgesetzt, dass die ursprüngliche Tabelle alle Partitionen der 10 enthält.
2. In der zweiten Gruppe wird von jedem Element die Zahl 1 subtrahiert. Da jede Partition 4 Summanden besitzt, werden dadurch sämtliche Partitionen der Zahl Z = 10 - 4 = 6 der Länge 4 dargestellt. Und auch hier erhält man alle Partitionen der Zahl 6 der Länge 4. (Versuchen Sie diesen Schritt an Tabelle 1 nachzuvollziehen!)

Abbildung 1 stellt die Aufteilung der Partitionen in zwei Gruppen dar und es ist nicht schwer, sie in eine Aussage über die Funktion p(Z, L) zu übersetzen; man erhält so die Rekursionsformel:

p(Z, L) = p(Z - 1, L - 1) + p(Z - L, L).

Abbildung 1: Graphische Darstellung der Vorgehensweise, wie die Partitionen einer Zahl Z der Länge L abgezählt werden können. Die Partitionen werden wie in Tabelle 1 spaltenweise angeordnet; die Summanden werden aufsteigend sortiert. Um eine Rekursionsformel herzuleiten, wird die Menge der Partitionen in zwei Gruppen zerlegt: Links diejenigen Partitionen, die mit einer 1 beginnen, rechts alle anderen Partitionen, die keine 1 enthalten können. In der linken Gruppe lassen sich unterhalb der ersten Zeile alle Partitionen von Z - 1 der Länge L - 1 identifizieren. In der zweiten Gruppe wird von jedem Summanden 1 subtrahiert. Dadurch entstehen alle Partitionen der Zahl Z - L der Länge L. Drückt man diese Überlegungen mit Hilfe der Funktion p(Z, L) aus, erhält man eine Rekursionsformel.

Für den Rekursionsanfang kann man mehrere Bedingungen formulieren:

1. Z ≤ 0:

Für Z = 0 kann man keine Partition bilden, da 0 als Summand nicht zugelassen ist. Dies wird auch für Z < 0 gefordert:

p(Z, L) = 0 für Z ≤ 0.

(Dass Z < 0 überhaupt aufgeführt wird, mag befremden. Aber da in der Rekursionsformel auf p(Z - L, L) zurückgegriffen wird und die Formel später numerisch ausgewertet wird, kann dieser Fall in einem Programm auftreten und sollte berücksichtigt werden.)

2. Z = 1:

Wenn Z = 1, kann die Partition nur einen Summanden besitzen und dieser muss gleich 1 sein, daher ist:

p(Z = 1, L) = 1 für L = 1 und p(Z = 1, L) = 0 für L > 1.

3. L > Z:

Da 0 kein erlaubter Summand ist, gilt:

p(Z, L) = 0 für L > Z.

4. L = Z:

Jetzt müssen alle Summanden gleich 1 sein und daher gilt:

p(Z, L) = 1 für L = Z.

Berechnung der Anzahl der Partitionen einer Zahl Z der Länge L

Im Kapitel über Kombinationen mit Wiederholungen wurden ähnliche Überlegungen wie hier angestellt, um eine Rekursionsformel herzuleiten. Dort konnte dann (Beweismethode "Stars and Bars") eine Formel für die Anzahl aller Möglichkeiten angegeben werden – die Berechnung erfolgte mit einem Binomialkoeffizienten. Hier liegt eine Rekursionsformel vor, die auf den ersten Blick ähnliche Struktur hat, aber bei genauer Betrachtung deutlich komplizierter ist. Denn im zweiten Summanden der Rekursionsformel p(Z - L, L) steht in der Differenz Z - L keine Konstante, die von Z abgezogen wird, sondern das Argument L der Funktion p(Z, L). Dieser Umstand verhindert, mit den bisher besprochenen Methoden eine explizite Lösung der Rekursionsformel anzugeben.

In den R-Skripten unten wird dann eine Funktion implementiert, die zu gegebenen Z und L die Anzahl p(Z, L) berechnet. Die Ergebnisse für Z, L ≤ 12 sind in Tabelle 2 zu sehen.

Tabelle 2: Die Anzahl der Partitionen p(Z, L) für 0 ≤ Z, L ≤ 12.

In Abbildung 2 werden die Werte als Histogramm dargestellt für 0 ≤ Z, L ≤ 30.

Abbildung 2: Histogramm für die Anzahl der Partitionen der Zahl Z mit Länge L. Rot eingetragen sind jeweils diejenigen L-Werte, bei denen zu gegebenem Z die Anzahl p(Z; L) maximal wird (wird das Maximum öfters angenommen, wird nur das erste Auftreten gekennzeichnet).

Berechnung der Anzahl der Partitionen einer Zahl Z

Wenn man p(Z, L) berechnen kann, ist es nicht mehr schwer, die Anzahl aller Partitionen p(Z) einer Zahl Z zu berechnen, also mit beliebiger Länge L (die Einschränkung, dass kein Summand gleich 0 sein darf, bleibt bestehen). Man muss jetzt nur über die möglichen Werte von p(Z, L) über L aufsummieren, also von L = 1 bis L = Z (siehe Abbildung 3).

Abbildung 3: Oben: Formel zur Berechnung von p(Z). Unten: Die Zahlenwerte von p(Z) für 0 ≤ Z ≤ 20.

Die Tabelle in Abbildung 3 zeigt die Werte von p(Z) für Z-Werte bis 20.

Ungeordnete Partitionen, bei denen 0 als Summand erlaubt ist

Bisher wurden Partitionen betrachtet, bei denen kein Summand gleich null sein darf. Interpretiert man dies als ein Abzählproblem, bei dem Kugeln auf Urnen verteilt werden, so bedeutet "kein Summand gleich null", dass keine Urne leer bleiben darf.

Die Summenformel aus Abbildung 3 kann aber auch anders interpretiert werden: Es sollen beliebig viele Urnen, zumindest mehr als Z, zur Verfügung stehen. Jeder Summand (mit Summationsindex L) steht für die Möglichkeit, dass lediglich L Urnen mit Kugeln gefüllt werden und alle anderen Urnen leer bleiben. Die obere Grenze der Summe kann beliebig erhöht werden, da p(Z, L) = 0 für L > Z.

Anders formuliert: Mehr als Z Urnen bieten keine neue Möglichkeiten, da die zusätzlichen Urnen leer bleiben müssen und somit keine neuen Lösungen des Abzählproblems entstehen. Und diese Argumentation ist natürlich wieder nur richtig, wenn die Urnen nicht unterscheidbar sind oder die Partitionen nicht unterschieden werden, wenn lediglich die Reihenfolge der Summanden vertauscht wird.

Zusammenfassung

Die Arten von Partitionen, die oben und in Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars besprochen wurden, sind nicht leicht zu unterscheiden. Um den Überblick zu bewahren, versuchen die folgenden drei Abbildungen (4 bis 6) die bisherigen Ergebnisse zusammenzufassen:

1. In Abbildung 4 werden am Beispiel Z = 4 und L = 2 die unterschiedlichen Arten von Partitionen gezeigt.
2. In Abbildung 5 werden die Formeln angegeben, wie die entsprechenden Partitionen abgezählt werden. Dabei ist zu beachten, dass für p(Z, L) keine explizite Formel, sondern nur die Rekursionsformel angegeben wurde. Und die geordneten Partitionen, bei denen der Summand 0 nicht erlaubt ist, lassen sich leicht auf den Fall zurückführen, wenn 0 erlaubt ist: Man legt je eine Kugel in die Urnen (dafür gibt es genau eine Möglichkeit) und zählt dann wie bei den Kombinationen mit Wiederholungen ("Stars and Bars").
3. In Abbildung 6 wird die Verbindung hergestellt zwischen den unterschiedlichen Arten von Partitionen und Abzählproblemen (mit Z Kugeln und L Urnen).

Abbildung 4: Darstellung der unterschiedlichen Arten von Partitionen für das Beispiel Z = 4 und L = 2. Die Partitionen sind in den Tabellen jeweils spaltenweise angeordnet.

Abbildung 5: Formeln zur Berechnung das Anzahl der Partitionen in den verschiedenen Fällen. Für p(Z, L) kann mit einfachen Mitteln keine explizite Formel hergeleitet werden, daher ist nur die Rekursionsformel angegeben.

Abbildung 6: Abzählprobleme formuliert mit Z Kugeln und L Urnen, die auf die unterschiedlichen Arten von Partitionen führen.

R-Skripte

Die Berechnung von p(Z, L)

Partitionen ohne den Summanden 0

In Abbildung 1 wurde die Rekursionsformel hergeleitet, die für die Anzahl der Partitionen p(Z, L) gilt. Zusammen mit dem Rekursionsanfang kann man jetzt leicht eine Funktion implementieren, die zu gegebenem Z und L die Anzahl p(Z, L) berechnet.

Naheliegend ist jetzt folgende Vorgehensweise: Man implementiert eine Funktion, etwa numberOfPartitions(Z, L) , mit den Eingabewerten Z und L und berechnet mit Hilfe der Rekursionsformel den Wert p(Z, L), der von numberOfPartitions() zurückgegeben wird.

Allerdings sollen später alle Partitionen zu gegebenem Z und L berechnet und als Matrix (etwa wie in Tabelle 1) zurückgegeben werden. Und diese Berechnung wird sehr oft die Funktion numberOfPartitions() aufrufen müssen – allerdings mit unterschiedlichen Eingabewerten. Dann wird aber bei jedem Aufruf von numberOfPartitions() die Rekursion von Neuem durchlaufen.

Es ist daher besser, eine Funktion zu entwickeln, die zu gegebenem Z und L alle Zahlenwerte p(z, l) mit z ≤ Z und l ≤ L berechnet. So wird die Rekursion nur einmal durchlaufen und man greift dann später auf die einmalig berechneten Werte p(z, l) zu.

Der Rückgabewert der zu entwickelnden Funktion ist dann eine Z × L Matrix, die oberhalb der Hauptdiagonale die Einträge 0 hat, p(z, l) = 0 für l > z.

Das folgende Listing zeigt einen Vorschlag, wie diese Funktion aussehen könnte:

numberOfPartitions <- function(Z = 2, L = Z){
  P <- matrix(data = 0, nrow = Z, ncol = L)
  
  P.mem <- function(Z, L){
    if(identical(L, 0)) return(0)
    if(Z <= 0 || L > Z) return(0)
    return(P[Z, L])
  }
  
  P[ , 1] <- 1
  for(i in seq_len(Z)){
    for(j in (2:L)){
      P[i, j] <- P.mem(Z = i - 1, L = j - 1) + P.mem(Z = i - j, L = j)
    }
  }
  return(P)
}

Zur Erklärung:

Zeile 1: Eingabewerte sind die Zahl Z und die Länge der Partition L. Da man alle Werte p(z, l) mit z ≤ Z und l ≤ L speichern möchte, wird man meist L = Z setzen; daher wurde dies als default-Wert für L vorgegeben.

Zeile 2 und 16: Es wird eine Z × L Matrix vorbereitet, die die gesuchten Anzahlen enthält und die am Ende zurückgegeben wird; die Matrix hat die Gestalt wie Tabelle 2.

Zeile 10: Wenn L = 1 ist, dann ist p(Z, L = 1) = 1 (Rekursionsanfang); daher kann man die erste Spalte der Matrix sofort setzen.

Zeile 11 bis 15: Die Doppelschleife iteriert außen über die Zeilen und innen über die Spalten der Matrix P, wobei die erste Spalte nicht mehr bearbeitet werden muss (der innere Schleifenindex startet bei j = 2).

Zeile 13: Im Schleifenkörper steht im Wesentlichen die Rekursionsformel für p(Z, L). Allerdings mit einem wichtigen Unterschied: Auf der rechten Seite wird auf die interne Funktion P.mem() zugegriffen (mem soll an memory erinnern). Dagegen wird auf der linken Seite tatsächlich die Matrix P gefüllt.

Zeile 4 bis 8: Die Funktion P.mem() gibt entweder den Rekursionsanfang zurück (Zeile 5 und 6) oder bereits berechnete Werte (Zeile 7).

Abbildung 7 zeigt die Werte von p(Z, L) für Z, L ≤ 25.

Abbildung 7: Die Anzahlen p(Z, L) der Partitionen der Zahl Z der Länge L, die mit der Funktion numberOfPartitions() aus dem letzten Skript berechnet wurden. Die Maximalwerte jeder Zeile sind gekennzeichnet (in Abbildung 2 waren sie rot dargestellt).

Partitionen mit dem Summanden 0

Soll eine Partition der Zahl Z die Länge L besitzen, aber beliebig viele Summanden dürfen den Wert 0 annehmen, so kann man aus Abbildung 7 sofort ersehen, wie die Anzahl dieser Partitionen zu berechnen ist: In jeder Zeile (die eine Zahl Z repräsentiert) werden die kumulierten Summen gebildet (siehe Formel in Abbildung 3).

Und diese kumulierten Summenwerte haben eine einfache Interpretation: Werden Z identische Kugeln auf L identische Urnen verteilt, wobei auch Urnen leer bleiben können, so beschreibt

• p(Z, 1) die Anzahl der Möglichkeiten, dass alle Kugeln in einer Urne liegen und L - 1 Urnen leer bleiben,
• p(Z, 2) die Anzahl der Möglichkeiten, dass alle Kugeln in zwei Urnen liegen und L - 2 Urnen leer bleiben und so weiter.

Soll jetzt wieder eine Funktion implementiert werden, die diese kumulierten Summen berechnet, so kann die Funktion numberOfPartitions() durch ein Argument zero = FALSE erweitert werden:

• Ist zero = FALSE , werden die Berechnungen wie oben ausgeführt.
• Ist zero = TRUE , werden die kumulierten Summen berechnet.

Dazu muss nur der Quelltext vor dem return-statement ergänzt werden (siehe Zeile 16 bis 19), um die Matrix der kumulierten Summen zu berechnen:

numberOfPartitions <- function(Z = 2, L = Z, zero = FALSE){
  P <- matrix(data = 0, nrow = Z, ncol = L)
  
  P.mem <- function(Z, L){
    if(identical(L, 0)) return(0)
    if(Z <= 0 || L > Z) return(0)
    return(P[Z, L])
  }
  
  P[ , 1] <- 1
  for(i in seq_len(Z)){
    for(j in (2:L)){
      P[i, j] <- P.mem(Z = i - 1, L = j - 1) + P.mem(Z = i - j, L = j)
    }
  }
  if(zero){
    # \sum_{i = 1}^{L} p(Z, i)
    P <- t(apply(X = P, MARGIN = 1, FUN = cumsum))
  }
  return(P)
}

Die folgende Abbildung 8 zeigt die Matrix (als Tabelle dargestellt), die durch den Aufruf entsteht:

numberOfPartitions(Z = 20, zero = TRUE)

Abbildung 8: Die Matrix, die mit der Funktion numberOfPartitions() erzeugt wurde. Z und L können hier Werte bis 20 annehmen.

Abbildung 9: Die kumulierten Summen der Anzahlen p(Z, L) der Partitionen der Zahl Z der Länge L dargestellt als Histogramm. Die Abbildung ist nur schwer mit Abbildung 2 zu vergleichen, da die z-Achsen unterschiedlich skaliert sind. Für Z und L wurden hier Werte bis 30 eingesetzt.

Die Berechnung aller Partitionen der Zahl Z der Länge L

In Tabelle 1 wurden für Z = 12 und L = 4 alle ungeordneten Partitionen angegeben, bei denen 0 als Summand nicht vorkommt. Im Folgenden soll ein Algorithmus entwickelt werden, der diese Aufgabe erledigt; er wird sich an der Vorgehensweise in Abbildung 1 orientieren.

Der Algorithmus

In Abbildung 1 werden zur Herleitung der Rekursionsformel für p(Z, L) die Partitionen von Z in zwei Gruppen zerlegt:

1. Partitionen, die eine 1 enthalten (die 1 kann dann auch öfters vorkommen).
2. Partitionen, die keine 1 enthalten.

Diese Aufteilung wird jetzt verwendet, um nicht nur die Partitionen zu zählen, sondern sie in einer Matrix abzuspeichern. Diese Matrix soll dann L Zeilen und p(Z, L) Spalten besitzen; das heißt die Partitionen werden spaltenweise angeordnet.

Die Funktion partitions() für diese Aufgabe ist im Listing unten dargestellt; sie besitzt die beiden Eingabewerte Z und L und die eben beschriebene Matrix als Rückgabewert.

Zur Vereinfachung ist aber die Funktion partitions() nicht rekursiv, sondern der rekursive Funktionsaufruf geschieht in der internen Funktion partitionsrec()_ (siehe Zeile 12 bis 40). Der Grund dafür liegt darin, dass man sehr oft auf die Anzahlen p(z, l) für 1 ≤ z, l ≤ Z zugreifen muss. Sämtliche dieser Anzahlen werden in partitions() zuerst berechnet und als Matrix abgespeichert (siehe Zeile 3). Der Zugriff auf diese Anzahlen erfolgt über eine weitere interne Funktion getNumberPart() (siehe Zeile 6 bis 9). Der Vorteil dieser internen Funktion liegt darin, dass man hier "unsinnige" Zugriffe abfangen kann (siehe Zeile 7).

partitions <- function(Z = 2, L = Z){
  stopifnot(Z > 0, L > 0)
  numbPart <- numberOfPartitions(Z = Z, L = L)
  
  # interne Fkt. zum Zugriff auf numbPart:
  getNumbPart <- function(Z = 2, L = Z){
    if(Z <= 0 || L <= 0) return(0)
    return(numbPart[Z, L])
  }
  
  # interne, rekursive Funktion:
  partitions_rec <- function(z, lgth){
    # Abbruchbedingung Länge 1:
    if(identical(lgth, 1)) return(as.matrix(z))
    
    # Matrizen vorbereiten:
    matrices <- vector(mode = "list", length = z)
    
    for( i in 0:(z-1) ){
      repetitions <- getNumbPart(Z = z - 1 - i*lgth, L = lgth-1)
      
      if(identical(repetitions, 0)){    # nichts zu tun: next()
        next()
      } else {
        v <- rep( x = i+1, times = repetitions )
      }
      
      # rekursiver Aufruf, um untere Teilmatrizen zu bilden:
      m.part <- i + partitions_rec(z = z - 1 - i*lgth, lgth = lgth - 1)
      
      if(is.null(m.part)){
        matrices[[i+1]] <- NULL
      } else {
        matrices[[i+1]] <- rbind(v, m.part)
      }
      
      dimnames(matrices[[i+1]]) <- NULL
    }
    return(Reduce(x = matrices, f = cbind))
  }
  
  return( partitions_rec(z = Z, lgth = L) )
}

Innerhalb der Funktion partitions() werden

1. die Eingabewerte geprüft (Zeile 2),
2. die Anzahlen p(z, l) berechnet und als Matrix gespeichert (Zeile 3) und
3. die Rekursion partitions_rec() aufgerufen (Zeile 42).

Die Vorgehensweise von partitions_rec(z, lgth) ist vermutlich in Abbildung 1 leichter zu verstehen als am Quelltext:

• Als Abbruchbedingung reicht es, den Fall zu behandeln, dass eine Partition der Zahl z der Länge 1 angefordert wird: dann wird z in eine Matrix verpackt und zurückgegeben (Zeile 14).
• Andernfalls wird eine Liste (der Länge z) von Matrizen vorbereitet (Zeile 17). Jede dieser Matrizen steht für Partitionen, die mit 1, 2, ..., z beginnen. Am Ende werden diese Matrizen mit Hilfe von Reduce() aneinandergefügt und zurückgegeben (Zeile 39).
• In der for-Schleife (Zeile 19 bis 38) werden die Matrizen mit Inhalten gefüllt; genauer es wird jeweils die erste Zeile gefüllt und die Berechnung der Teilmatrizen (also die Teile unter der ersten Zeile) an die Rekursion weitergereicht.
• Um die erste Zeile einer dieser Matrizen zu erzeugen, muss man nur wissen, wie oft die Werte 1, 2, ..., z vorkommen können; aber dies lässt sich an den Zahlen p(z, l) ablesen (siehe Zeile 20, dieser Schritt ist sicher in Abbildung 1 leichter zu verstehen!).
• Anschließend wird die ersten Zeile der Teilmatrizen gebildet (Zeile 22 bis 26) und die Rekursion aufgerufen (Zeile 29).
• Die erste Zeile und die zugehörige Teilmatrix wird aneinandergefügt (Zeile 31 bis 35).

Hier ein Beispiel für den Aufruf von partitions():

partitions(Z = 15, L = 5)
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20]
# [1,]    1    1    1    1    1    1    1    1    1     1     1     1     1     1     1     1     1     1     1     1
# [2,]    1    1    1    1    1    1    1    1    1     1     1     1     1     1     2     2     2     2     2     2
# [3,]    1    1    1    1    1    1    2    2    2     2     3     3     3     4     2     2     2     2     3     3
# [4,]    1    2    3    4    5    6    2    3    4     5     3     4     5     4     2     3     4     5     3     4
# [5,]   11   10    9    8    7    6    9    8    7     6     7     6     5     5     8     7     6     5     6     5
#      [,21] [,22] [,23] [,24] [,25] [,26] [,27] [,28] [,29] [,30]
# [1,]     1     1     1     2     2     2     2     2     2     3
# [2,]     2     3     3     2     2     2     2     2     3     3
# [3,]     4     3     3     2     2     2     3     3     3     3
# [4,]     4     3     4     2     3     4     3     4     3     3
# [5,]     4     5     4     7     6     5     5     4     4     3

Beurteilung des Algorithmus

Der oben vorgestellte Algorithmus zur rekursiven Berechnung aller Partitionen setzt die Vorgehensweise um, wie in Abbildung 1 die Rekursionsformel für p(Z, L) hergeleitet wurde – und daher erscheint seine Logik leicht verständlich. Es soll aber darauf hingewiesen werden, dass der Algorithmus nur eingesetzt werden sollte, um für kleine Zahlen Z die Partitionen zu berechnen, wobei "klein" hier etwa Z < 50 bedeutet. Denn bei jedem rekursiven Aufruf wird eine neue Liste von Matrizen angelegt und diese Liste muss bis zum Ende der Rekursion gespeichert werden. Dadurch wird sehr viel Speicherplatz und Rechenzeit verschwendet.

Möchte man die Partitionen für größere Z berechnen, sollte man sich einen Algorithmus überlegen, der diese Nachteile nicht besitzt. Dabei muss man aber bedenken: Verfolgt man in Abbildung 2 die "rote Spur" der Maximalwerte von p(Z, L), so ist klar, dass sie überproportional zu Z ansteigen. Das heißt aber, dass auch ein schneller Algorithmus, der alle Partitionen zu L und Z berechnen soll, ein sehr großes Objekt als Rückgabewert erzeugen wird.

Ein verbesserter Algorithmus zur Berechnung aller Partitionen einer Zahl Z der Länge L

Im letzten Skript wurde der Aufruf partitions(Z = 15, L = 5) gezeigt, wodurch 30 Partitionen erzeugt wurden, also eine 5 × 30 Matrix. So wie der Algorithmus zum Aufbau dieser Matrix arbeitet, werden die Partitionen automatisch in lexikographischer Anordnung in die Matrix geschrieben. Dies kann man als Ausgangspunkt nehmen, um einen schnelleren Algorithmus herzuleiten – allerdings soll dies hier nur stückweise geschehen, die Hauptarbeit sei dem Leser zur Übung überlassen.

Aufgabe: Beschreiben Sie, welche Operation man ausführen muss, um zu einer gegebenen Partition von Z der Länge L, also

Z = z₁ + ... + z_L, mit z₁ ≤ z₁ ≤ ... ≤ z_L,

diejenige Partition zu erzeugen, die in lexikographischer Anordnung auf die gegebene Partition folgt.

Hinweis: Untersucht man die Partitionen, die im letzten Skript erzeugt wurden, so erkennt man: Geht man vom letzten Summanden z_L aus rückwärts durch die Partition, so gibt es einen ersten Index i, so dass sich z_L und z_i um 2 oder mehr unterscheiden.

Vergleicht man nun diese Partition mit der darauf folgenden Partition, so sind die Summanden

z₁, ..., z_i-1

unverändert, dagegen haben die Summanden

z_i, ..., z_L

der nächsten Partition andere Werte.

Wie kann man aus der gegebenen Partition die folgende Partition berechnen?

♦ ♦ ♦ ♦ ♦

Die Funktion partitionsLex() im folgenden Skript setzt genau diesen Algorithmus um; der Rückgabewert ist wieder als Matrix aufgebaut mit L Zeilen und p(Z, L) Spalten:

partitionsLex <- function(Z = 2, L = Z){
  stopifnot(Z > 0, L > 0)
  stopifnot(Z >= L) 
  # 1. Matrix vorbereiten; 1. Spalte setzen:
  ncls <- numberOfPartitions(Z = Z, L = Z)[Z, L]
  m <- matrix( data = 0, nrow = L, ncol = ncls )
  if(identical(L, 1)){
    m[ , 1] <- Z
    return(m)
  }
  m[ , 1] <- c( rep(x = 1, times = L - 1), Z - L + 1   )
  
  # 2.  interne Funktion nextPartition():
  nextPartition <- function(v){
    if( identical(Z - L, 1) ){    # es gibt nur eine Partition
      return(NULL)
    }
    w <- v
    for( j in ((L-1):1) ){    # Iteration über die vorderen Elemente
      if( v[L] - v[j] > 1 ){
        idx <- (j:(L-1))
        if( identical(length(idx) , 0L) ){
          break()
        } else {
          w[idx] <- v[j] + 1
          w[L] <- Z - sum(w[-L])
          break()
        }
      }
    }   # Ende Schleife

    if( all(v == w) ){
      return(NULL)
    } else {
      return(w)
    }
  }    # Ende nextPartition()
  
  
  # 3. eigentlicher Algorithmus als for-Schleife und Rückgabe m:
  v <- m[ , 1]
  if(identical(ncls, 1)){
    return(m)
  } else {
    for(i in (2:ncls)){
      v <- nextPartition(v)
      m[ , i] <- v
    }
    return(m)
  }
}

Und hier zwei Beispiele für den Aufruf von partitionsLex():

# Ausgabe aller Partitionen von Z = 8 beliebiger Länge (Matrizen in Liste verpackt):
sapply(X = (1:8), FUN = function(x){return(partitionsLex(Z = 8, L = x))})
# [[1]]
#      [,1]
# [1,]    8
# 
# [[2]]
#      [,1] [,2] [,3] [,4]
# [1,]    1    2    3    4
# [2,]    7    6    5    4
# 
# [[3]]
#      [,1] [,2] [,3] [,4] [,5]
# [1,]    1    1    1    2    2
# [2,]    1    2    3    2    3
# [3,]    6    5    4    4    3
# 
# [[4]]
#      [,1] [,2] [,3] [,4] [,5]
# [1,]    1    1    1    1    2
# [2,]    1    1    1    2    2
# [3,]    1    2    3    2    2
# [4,]    5    4    3    3    2
# 
# [[5]]
#      [,1] [,2] [,3]
# [1,]    1    1    1
# [2,]    1    1    1
# [3,]    1    1    2
# [4,]    1    2    2
# [5,]    4    3    2
# 
# [[6]]
#      [,1] [,2]
# [1,]    1    1
# [2,]    1    1
# [3,]    1    1
# [4,]    1    1
# [5,]    1    2
# [6,]    3    2
# 
# [[7]]
#      [,1]
# [1,]    1
# [2,]    1
# [3,]    1
# [4,]    1
# [5,]    1
# [6,]    1
# [7,]    2
# 
# [[8]]
#      [,1]
# [1,]    1
# [2,]    1
# [3,]    1
# [4,]    1
# [5,]    1
# [6,]    1
# [7,]    1
# [8,]    1

numberOfPartitions(Z = 50, L = 15)[50, 15]
# 12801
partitionsLex(Z = 50, L = 15)[ , 6400]
# [1]  1  1  1  1  1  1  3  3  3  3  3  4  4  7 14