Partitionen einer natürlichen Zahl

1. Aufgabe

Wir beschäftigen uns in dieser Aufgabe mit der Fragestellung, auf wie viele Arten sich eine natürliche Zahl als Summe von natürlichen Zahlen – auch Partition oder Zerlegung genannt – schreiben lässt? Wir präzisieren die Fragestellung noch mit folgender Ergänzung: Zwei Zerlegungen, die sich nur in der Reihenfolge ihrer Summanden unterscheiden, gelten als gleich. Konkret: Die Zerlegungen der ersten fünf natürlichen Zahlen sehen so aus:

1 = 1
2 = 2
2 = 1 + 1
3 = 3
3 = 2 + 1
3 = 1 + 1 + 1
4 = 4
4 = 3 + 1
4 = 2 + 2
4 = 2 + 1 + 1
4 = 1 + 1 + 1 + 1
5 = 5
5 = 4 + 1
5 = 3 + 2
5 = 3 + 1 + 1
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

1.1. Die Klasse Partition

Die algorithmische Bestimmung aller Partitionen einer natürlichen Zahl ist keineswegs trivial, wie man bei anfänglicher Betrachtung vielleicht glauben mag. Mit Hilfe des rekursiven Methodenaufrufs lässt sich das Problem am ehesten vergleichsweise einfach lösen. Zu diesem Zweck entwerfen wir zunächst eine Klasse Partition. Objekte dieser Klasse beschreiben eine einzelne Zerlegung einer natürlichen Zahl, also zum Beispiel

3 + 1 + 1

als eine mögliche Zerlegung der Zahl 5. Implementieren Sie die Klasse Partition an Hand der Spezifikation aus Tabelle 1. Die einzelnen Summanden einer Partition könnten in einem Partition-Objekt in einem Array abgelegt sein.

Element

Schnittstelle und Beschreibung

Konstruktor

public Partition (int[] numbers);

Erzeugt ein Partition-Objekt auf Basis der Summanden des Arrays numbers. Um Partition-Objekte miteinander vergleichen zu können, sollten die Summanden in einem Partition-Objekte stets sortiert in absteigender Reihenfolge vorliegen.

Eigenschaft Number

public int Number { get; };

Liefert die zur Partition gehörende natürliche Zahl zurück.

Eigenschaft Length

public int Length { get; };

Liefert die Anzahl der Summanden der Partition zurück.

Eigenschaft Numbers

public int[] Numbers { get; };

Liefert die einzelnen Summanden der Partition in einem Array zurück. Hinweis: Sollten die Summanden im aktuellen Objekt in einem Array abgelegt sein, so ist eine Kopie dieses Arrays zu erstellen. Andernfalls ist der Zustand des aktuellen Objekts nicht geschützt (Rückgabe der Referenz des Originalarrays)!

Methode Equals

public override bool Equals(Object o);

Vergleicht zwei Partition-Objekte auf Gleichheit. Siehe dazu die Definition der Gleichheit zweier Zerlegungen in der Einführung.

Methode ToString

public override String ToString();

Die Darstellung einer Partition durch eine Zeichenkette sollte folgendes Aussehen haben:

7 = 3 + 2 + 1 + 1

Tabelle 1. Elemente der Klasse Partition.


Neben den in Tabelle 1 beschriebenen Elementen der Klasse Partition sollten Partition-Objekte auch kopierbar sein. Welche .NET-Standardschnittstelle ist aus diesem Grund zu implementieren? Zur Überprüfung Ihrer Implementierung sollten die folgenden Codefragmente wie beschrieben ausführbar sein:

Beispielfragment 1:

int[] numbers = { 2 };
Partition p1 = new Partition(numbers);
Console.WriteLine(p1);
numbers = new int[] { 1, 1 };
Partition p2 = new Partition(numbers);
Console.WriteLine(p2);

Ausgabe:

2 = 2
2 = 1 + 1

Beispielfragment 2:

int[] numbers = { 1, 2, 3 };
Partition p1 = new Partition(numbers);
Console.WriteLine(p1);
numbers = new int[] { 3, 2, 1 };
Partition p2 = new Partition(numbers);
Console.WriteLine(p2);
Console.WriteLine(p1.Equals(p2));

Ausgabe:

6 = 3 + 2 + 1
6 = 3 + 2 + 1
True

Beispielfragment 3:

int[] numbers = { 2, 4, 6 };
for (int i = 0; i < numbers.Length; i++)
    Console.Write("{0} ", numbers[i]);
Console.WriteLine();
Partition p = new Partition(numbers);
int[] numbers1 = p.Numbers;
for (int i = 0; i < numbers1.Length; i++)
    Console.Write("{0} ", numbers1[i]);

Ausgabe:

2 4 6
6 4 2

1.2. Partitionen vergleichen

Unterschiedliche Zerlegungen derselben natürlichen Zahl lassen sich vergleichen. Welche Standardschnittstelle des .NET-Objektmodells und welche Operatoren sollten Sie zu diesem Zweck in der Klasse Partition implementieren? Erkennen Sie am folgenden Beispiel aller Zerlegungen der Zahl 7, wie der Vergleich zweier Partitionen definiert sein könnte?

7 = 7
7 = 6 + 1
7 = 5 + 2
7 = 5 + 1 + 1
7 = 4 + 3
7 = 4 + 2 + 1
7 = 4 + 1 + 1 + 1
7 = 3 + 3 + 1
7 = 3 + 2 + 2
7 = 3 + 2 + 1 + 1
7 = 3 + 1 + 1 + 1 + 1
7 = 2 + 2 + 2 + 1
7 = 2 + 2 + 1 + 1 + 1
7 = 2 + 1 + 1 + 1 + 1 + 1
7 = 1 + 1 + 1 + 1 + 1 + 1 + 1

Der Vergleich zweier Partitionen erfolgt Summand für Summand, beginnend mit dem ersten Summanden. Nur wenn diese gleich sind, wird der zweite (ggf. dritte, usw.) Summand betrachtet. Der größere Summand gehört zur größeren Partition.

Beispielfragment:

Partition p1 = new Partition (new int[] { 3, 1, 1, 1, 1 });
Partition p2 = new Partition (new int[] { 2, 2, 2, 1});
Console.WriteLine(p1);
Console.WriteLine(p2);
Console.WriteLine(p1.CompareTo(p2));
Console.WriteLine(p2.CompareTo(p1));

Ausgabe:

7 = 3 + 1 + 1 + 1 + 1
7 = 2 + 2 + 2 + 1
1
-1

Hinweis: Offensichtlich ergibt es nur Sinn, Partitionen derselben natürlichen Zahl zu vergleichen. Den Vergleich von Partitionen verschiedener natürlicher Zahlen brauchen Sie in dieser Aufgabe nicht zu berücksichtigen.

Zum Sortieren benötigen wir natürlich mehrere Partitionen. Die Implementierung des Sortierens ist deshalb Bestandteil der Klasse PartitionSet, die wir nun betrachten.

1.3. Die Klasse PartitionSet

Die Menge aller Partitionen einer natürlichen Zahl wird in einem Objekt der Klasse PartitionSet zusammengefasst (Tabelle 2). Da der Umfang dieser Menge nicht ohne weiteres vorab berechenbar ist, sollten Sie zum Abspeichern der Zerlegungen eine listenartige Standardklasse verwenden, die eine beliebige Anzahl von Objekten aufnehmen kann.

Element

Schnittstelle und Beschreibung

Konstruktor

public PartitionSet (int number);

Erzeugt ein PartitionSet-Objekt zur natürlichen Zahl number. Die einzelnen Partition-Objekte, deren Berechnung noch aussteht, sind mit der Insert-Methode in die Partitionenliste des aktuellen Objekts aufzunehmen, siehe dazu weiter unten.

Eigenschaft Number

public int Number { get; };

Liefert die natürliche Zahl zurück, deren Partitionen betrachtet werden.

Eigenschaft Count

public int Count { get; };

Liefert die Anzahl der Partitionen zurück, die die natürliche Zahl (siehe Eigenschaft Number) besitzt.

Methode Contains

public bool Contains (Partition p);

Liefert true zurück, wenn die Partition p bereits in der Partitionenliste des Objekts enthalten ist, andernfalls false.

Methode Insert

public void Insert (Partition p);

Fügt die Partition p in die aktuelle Partitionenliste ein. In dieser Liste dürfen Partitionen nicht mehrfach enthalten sein. Ein Aufruf von Insert sollte also stets durch einen Aufruf von Contains geschützt werden.

Indexer

public Partition this [int index] { get; }

Der Indexer liefert die Partition an der spezifizierten Position index aus der aktuellen Partitionenliste zurück.

Methode SortAscending

public void SortAscending ();

Sortiert die Liste aller Partitionen des aktuellen Objekts in aufsteigender Reihenfolge. Die Art und Weise, wie Partitionen verglichen werden, wurde im letzten Abschnitt erläutert!

Methode SortDescending

public void SortDescending ();

Sortiert die Liste aller Partitionen des aktuellen Objekts in absteigender Reihenfolge.

Methode ToString

public override String ToString ();

Fasst alle Partitionen des Objekts zu einer Zeichenkette zusammen. Die Darstellung sollte – am Beispiel der Zahl 3 gezeigt – folgendes Aussehen haben:

1: 3 = 3
2: 3 = 2 + 1
3: 3 = 1 + 1 + 1

Tabelle 2. Elemente der Klasse PartitionSet.


Die Klasse PartitionSet aus Tabelle 2 ist noch nicht in der Lage, die Partitionen zu einer beliebigen natürlichen Zahl zu berechnen. Darauf kommen wir im folgenden Abschnitt zu sprechen. Die prinzipielle Funktionsweise der Klasse PartitionSet lässt sich aber schon „manuell“ testen:

Beispielfragment 1:

PartitionSet ps = new PartitionSet(3);

// add partitions of number 3 manually
Partition p;
p = new Partition(new int[] { 3 });
ps.Insert(p);
p = new Partition(new int[] { 1, 2 });
ps.Insert(p);
p = new Partition(new int[] { 1, 1, 1 });
ps.Insert(p);
Console.WriteLine(ps);

Ausgabe:

1: 3 = 3
2: 3 = 2 + 1
3: 3 = 1 + 1 + 1

Das folgende Beispielfragment besitzt dieselbe Ausgabe! Beachten Sie, dass die Partitionen eines PartitionSet-Objekts durch einen Aufruf der SortDescending-Methode sortiert werden:

Beispielfragment 2:

PartitionSet ps = new PartitionSet(3);

// add partitions of number 3 manually
// (note order of 'Insert' calls)
Partition p;
p = new Partition(new int[] { 1, 1, 1 });
ps.Insert(p);
p = new Partition(new int[] { 2, 1 });
ps.Insert(p);
p = new Partition(new int[] { 3 });
ps.Insert(p);
ps.SortDescending();    // sorting partitions
Console.WriteLine(ps);

1.4. Rekursive Berechnung aller Partitionen einer natürlichen Zahl

Wir kommen nun auf das Kernstück der Aufgabe zu sprechen, die algorithmische Berechnung aller Partitionen zu einer vorgegebenen natürlichen Zahl. Ist n die zu Grunde liegende natürliche Zahl, so gehen wir davon aus, dass mittels Rekursion die Menge aller Partitionen der Zahl n-1 bereits vorliegt. Da für n = 1 diese Berechnung trivial ist, stellt diese Annahme keine Einschränkung dar!

Haben wir alle Partitionen der Zahl n-1 vorliegen, so lassen sich wie folgt alle Partitionen der Zahl n trivial berechnen: Wir nehmen eine beliebige Partition der Zahl n-1 zur Hand. Ihre Anzahl der Summanden sei m. Wenn wir der Reihe nach zu jedem einzelnen dieser m Summanden den Wert 1 addieren, erhalten wir auf einen Schlag m Partitionen der Zahl n! Um es am folgenden Beispiel zu demonstrieren: Ist

4 + 2 + 2

eine Partition der Zahl 8, so erhalten wir sofort die drei Partitionen

(4+1) + 2 + 2 = 5 + 2 + 2
4 + (2+1) + 2 = 4 + 3 + 2
4 + 2 + (2+1) = 4 + 2 + 3 = 4 + 3 + 2

der natürlichen Zahl 9. Der einzige Nachteil dieses Ansatzes ist bereits erkennbar: Wir können auf diese Weise mehrfach dieselbe Partition erhalten, wie das Beispiel zeigt. Dies stellt aber kein echtes Problem dar. Wir müssen bei der Konstruktion der Partitionenmenge nur darauf achten, dass beim Einfügen neu berechneter Partitionen diese nicht schon in der vorliegenden Partitionenmenge enthalten sind.

Man kann sich leicht überlegen, dass bei vorliegender Partitionenmenge einer Zahl n-1 auf diese Weise alle Partitionen der Zahl n berechnet werden – mit einer Ausnahme: Die Partition

1 + 1 + ... + 1    // n summands

wird nicht konstruiert, da bei allen berechneten Partitionen mindestens ein Summand immer den Wert 2 besitzt. In der Tat ist die fehlende Partitionen einer Zahl n, die aus n 1-en besteht, noch nachträglich in die Partitionenmenge aufzunehmen.

In Abbildung 1 finden Sie eine Beschreibung des Algorithmus in Gestalt von Pseudocode vor:

Pseudocode zur Berechnung aller Partitionen einer natürlichen Zahl.

Abbildung 1. Pseudocode zur Berechnung aller Partitionen einer natürlichen Zahl.


Implementieren Sie in diesem Abschnitt eine Methode Calculate zur Berechnung aller Partitionen einer natürlichen Zahl und ordnen Sie diese einer separaten Klasse PartitionsCalculator zu (Tabelle 3):

Element

Schnittstelle und Beschreibung

Methode Calculate

public static PartitionSet Calculate (int n);

Berechnet die Menge aller Partitionen der Zahl n an Hand des in Abbildung 1 beschriebenen Algorithmus. Das Ergebnis wird durch den Rückgabewert (Objekt vom Typ PartitionSet) zurückgeliefert.

Tabelle 3. Elemente der Klasse PartitionsCalculator.


Es folgen zwei Beispielfragmente zum Testen Ihrer Realisierung der Klasse PartitionsCalculator:

Beispielfragment 1:

PartitionSet set = PartitionsCalculator.Calculate(6);
Console.WriteLine("Partitions of {0}:", set.Number);
Console.WriteLine("{0}", set);

Ausgabe:

Partitions of 6:
 1: 6 = 6
 2: 6 = 5 + 1
 3: 6 = 4 + 2
 4: 6 = 3 + 3
 5: 6 = 4 + 1 + 1
 6: 6 = 3 + 2 + 1
 7: 6 = 2 + 2 + 2
 8: 6 = 3 + 1 + 1 + 1
 9: 6 = 2 + 2 + 1 + 1
10: 6 = 2 + 1 + 1 + 1 + 1
11: 6 = 1 + 1 + 1 + 1 + 1 + 1

Beispielfragment 2:

PartitionSet set = PartitionsCalculator.Calculate(6);
set.Sort();
Console.WriteLine("Partitions of {0}:", set.Number);
Console.WriteLine("{0}", set);

Ausgabe:

Partitions of 6:
 1: 6 = 6
 2: 6 = 5 + 1
 3: 6 = 4 + 2
 4: 6 = 4 + 1 + 1
 5: 6 = 3 + 3
 6: 6 = 3 + 2 + 1
 7: 6 = 3 + 1 + 1 + 1
 8: 6 = 2 + 2 + 2
 9: 6 = 2 + 2 + 1 + 1
10: 6 = 2 + 1 + 1 + 1 + 1
11: 6 = 1 + 1 + 1 + 1 + 1 + 1

Ein Vergleich der zwei Ausgaben zeigt, dass der Algorithmus die Partitionen zunächst in unsortierter Reihenfolge erzeugt. Mit einem Aufruf von Sort schaffen wir Ordnung in der Menge aller Partitionen.

1.5. Anzahl der Partitionen

Die Anzahl der Partitionen einer natürlichen Zahl haben Sie mit Hilfe des letzten Teilschritts als Nebeneffekt berechnet. Es gibt aber auch eine alternative Möglichkeit mit Hilfe einer rekursiven Formel, also ohne die Partitionen selbst bestimmen zu müssen. Wir führen zu diesem Zweck die Bezeichnung sum(n) für die gesuchte Anzahl ein. Ferner sei b(n,m) die Anzahl der Zerlegungen von n, in denen der größte Summand gleich m ist. Also an einem Beispiel erläutert: In der Menge aller Partitionen von 5

1: 5 = 5
2: 5 = 4 + 1
3: 5 = 3 + 2
4: 5 = 3 + 1 + 1
5: 5 = 2 + 2 + 1
6: 5 = 2 + 1 + 1 + 1
7: 5 = 1 + 1 + 1 + 1 + 1

finden wir insgesamt sum(5) = 7 Zerlegungen vor. Für die Anzahl der Zerlegungen von 5, in denen der größte Summand gleich m (m = 1,2,3,4 und 5) ist, gilt hier

b(5,1) = 1
b(5,2) = 2
b(5,3) = 2
b(5,4) = 1
b(5,5) = 1

Offensichtlich gilt nun

sum(n) = b(n,1) + b(n,2) + b(n,3) + .... + b(n,n-1) + b(n,n).

Weiter muss man nicht gehen, denn b(n,n+1), b(n,n+2) sind ja alle 0. Bleibt noch die Frage nach der Berechnung von b(n,m). Hier gilt folgende rekursive Formel:

b(n,m) = b(n-1,m-1) + b(n-m,m).

Wenn Sie die folgenden Anfangsbedingungen berücksichtigen, von deren Korrektheit man sich leicht überzeugen kann, steht einer einfachen, direkten Umsetzung in eine rekursive C#-Methode NumberOfPartitions (Tabelle 4) nichts mehr im Weg:

b(n,m) = 0, wenn m > n.

b(n,0) = 0, für alle n > 0.

b(n,1) = 1, für alle n > 0.

Element

Schnittstelle und Beschreibung

Methode NumberOfPartitions

public static int NumberOfPartitions(int n, int maxSummand);

Berechnet die Anzahl aller Partitionen zur Zahl n, die einen maximalen Summanden maxSummand besitzen.

Methode NumberOfPartitions

public static int NumberOfPartitions(int n);

Berechnet die Anzahl aller Partitionen zur Zahl n.

Tabelle 4. Weitere Elemente der Klasse PartitionsCalculator.

1.6. Partitionen aufzählen

Für das Auflisten aller Partitionen einer natürlichen Zahl gibt es im .NET-Objektmodell konzeptionelle Vorgaben. Ergänzen Sie Ihre Implementierung der Klasse PartitionSet entsprechend.

Beispielfragment:

PartitionSet set = PartitionsCalculator.Calculate(5);
if (set is IEnumerable)
{
    IEnumerator ienum = set.GetEnumerator();

    Console.WriteLine("Partitions of {0}:", set.Number);
    while (ienum.MoveNext())
    {
        Partition p = (Partition)ienum.Current;
        Console.WriteLine(p);
    }
}

Ausgabe:

Partitions of 5:
5 = 5
5 = 4 + 1
5 = 3 + 2
5 = 3 + 1 + 1
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

2. Lösung

Quellcode: Siehe auch github.com/peterloos/CSharp_Partitions.git.

Auf Grund der sehr ausführlich gehaltenen Aufgabenstellung begnügen wir uns damit, die Implementierung der drei betrachteten Klassen ohne zusätzliche Erläuterungen wiederzugeben:

001: class Partition : IComparable, ICloneable
002: {
003:     private int[] numbers;
004: 
005:     // c'tor
006:     public Partition()
007:     {
008:         this.numbers = new int[1];
009:         this.numbers[0] = 0;
010:     }
011: 
012:     public Partition(int[] numbers)
013:     {
014:         this.numbers = (int[])numbers.Clone();
015:         Array.Sort(this.numbers);
016:         Array.Reverse(this.numbers);
017:     }
018: 
019:     // properties
020:     public int Number
021:     {
022:         get
023:         {
024:             int number = this.numbers[0];
025:             for (int i = 1; i < this.numbers.Length; i++)
026:                 number += this.numbers[i];
027:             return number;
028:         }
029:     }
030: 
031:     public int Length
032:     {
033:         get
034:         {
035:             return this.numbers.Length;
036:         }
037:     }
038: 
039:     public int[] Numbers
040:     {
041:         get
042:         {
043:             return (int[]) this.numbers.Clone();
044:         }
045:     }
046: 
047:     // overrides
048:     public override String ToString()
049:     {
050:         if (this.numbers.Length == 0)
051:             return "";
052: 
053:         StringBuilder tmp = new StringBuilder();
054:         tmp.AppendFormat("{0} = {1}", this.Number, this.numbers[0]);
055:         for (int i = 1; i < this.numbers.Length; i++)
056:             tmp.AppendFormat(" + {0}", this.numbers[i]);
057:         return tmp.ToString();
058:     }
059: 
060:     public override bool Equals(Object o)
061:     {
062:         if (!(o is Partition))
063:             throw new ArgumentException("Wrong parameter type");
064: 
065:         Partition p = (Partition) o;
066: 
067:         // partitions of different numbers can't be equal
068:         if (this.Number != p.Number)
069:             return false;
070: 
071:         // partitions with a different number of summands can't be equal
072:         if (this.Length != p.Length)
073:             return false;
074: 
075:         // compare summands
076:         for (int i = 0; i < this.numbers.Length; i++)
077:             if (this.numbers[i] != p.numbers[i])
078:                 return false;
079: 
080:         return true;
081:     }
082: 
083:     public override int GetHashCode()
084:     {
085:         return this.numbers.GetHashCode();
086:     }
087: 
088:     // implementation of interface 'IComparable'
089:     public int CompareTo(Object o)
090:     {
091:         if (!(o is Partition))
092:             throw new ArgumentException("Wrong parameter type");
093: 
094:         Partition p = (Partition)o;
095: 
096:         if (this.Number != p.Number)
097:             throw new ArgumentException("Number of partitions doesn't match");
098: 
099:         if (this.Equals(p))
100:             return 0;
101: 
102:         int min = (this.numbers.Length > p.numbers.Length) ?
103:             p.numbers.Length : this.numbers.Length;
104: 
105:         for (int i = 0; i < min; i++)
106:         {
107:             if (this.numbers[i] > p.numbers[i])
108:                 return 1;
109:             if (this.numbers[i] < p.numbers[i])
110:                 return -1;
111:         }
112: 
113:         return 0;
114:     }
115: 
116:     public static bool operator ==(Partition p1, Partition p2)
117:     {
118:         return p1.Equals(p2);
119:     }
120: 
121:     public static bool operator !=(Partition p1, Partition p2)
122:     {
123:         return !(p1 == p2);
124:     }
125: 
126:     public static bool operator <(Partition p1, Partition p2)
127:     {
128:         return p1.CompareTo(p2) < 0;
129:     }
130: 
131:     public static bool operator <=(Partition p1, Partition p2)
132:     {
133:         return p1.CompareTo(p2) <= 0;
134:     }
135: 
136:     public static bool operator >(Partition p1, Partition p2)
137:     {
138:         return !(p1 <= p2);
139:     }
140: 
141:     public static bool operator >=(Partition p1, Partition p2)
142:     {
143:         return !(p1 < p2);
144:     }
145: 
146:     // implementation of interface 'ICloneable'
147:     public Object Clone()
148:     {
149:         return new Partition(this.numbers);
150:     }
151: }

Beispiel 1. Klasse Partition.


001: class PartitionSet : IEnumerable, IEnumerator
002: {
003:     private int number;
004:     private List<Partition> partitions;
005:     private int index;
006: 
007:     public PartitionSet(int number)
008:     {
009:         this.number = number;
010:         this.partitions = new List<Partition>();
011:         this.index = -1;
012:     }
013: 
014:     // number
015:     public int Number
016:     {
017:         get
018:         {
019:             return this.number;
020:         }
021:     }
022: 
023:     // number of partitions
024:     public int Count
025:     {
026:         get
027:         {
028:             return this.partitions.Count;
029:         }
030:     }
031: 
032:     // indexer
033:     public Partition this[int i]
034:     {
035:         get
036:         {
037:             return (Partition) this.partitions[i].Clone();
038:         }
039:     }
040: 
041:     // public interface
042:     public void Insert(Partition p)
043:     {
044:         if (! this.partitions.Contains(p))
045:             this.partitions.Add(p);
046:     }
047: 
048:     public bool Contains(Partition p)
049:     {
050:         return this.partitions.Contains (p);
051:     }
052: 
053:     public void SortDescending()
054:     {
055:         this.partitions.Sort();
056:         this.partitions.Reverse();
057:     }
058: 
059:     public void SortAscending()
060:     {
061:         this.partitions.Sort();
062:     }
063: 
064:     // overrides
065:     public override String ToString()
066:     {
067:         StringBuilder sb = new StringBuilder();
068:         String format = (this.partitions.Count < 10) ?
069:             "{0}: {1}" : "{0,2}: {1}";
070:         for (int i = 0; i < this.partitions.Count; i++)
071:         {
072:             sb.AppendFormat(format, i + 1, this.partitions[i]);
073:             sb.AppendLine();
074:         }
075:         return sb.ToString();
076:     }
077: 
078:     // implementation of interface 'IEnumerable'
079:     public IEnumerator GetEnumerator()
080:     {
081:         this.SortAscending();
082:         return this;
083:     }
084:     
085:     // implementation of interface 'IEnumerator'
086:     public Object Current
087:     {
088:         get
089:         {
090:             return this.partitions[this.index];
091:         }
092:     }
093: 
094:     public bool MoveNext()
095:     {
096:         this.index++;
097:         if (this.index < this.partitions.Count)
098:         {
099:             return true;
100:         }
101:         else
102:         {
103:             this.index = -1;
104:             return false;
105:         }
106:     }
107: 
108:     public void Reset()
109:     {
110:         this.index = -1;
111:     }
112: }

Beispiel 2. Klasse PartitionSet.


01: class PartitionsCalculator
02: {
03:     public static int NumberOfPartitions(int number)
04:     {
05:         if (number < 1)
06:             return 0;
07: 
08:         int total = 0;
09: 
10:         for (int maxSummand = 1; maxSummand <= number; maxSummand++)
11:             total += NumberOfPartitions(number, maxSummand);
12: 
13:         return total;
14:     }
15: 
16:     public static int NumberOfPartitions(int number, int maxSummand)
17:     {
18:         if (maxSummand > number)
19:         {
20:             return 0;
21:         }
22:         else if (maxSummand == 0)
23:         {
24:             return 0;
25:         }
26:         else if (maxSummand == 1)
27:         {
28:             return 1;
29:         }
30:         else
31:         {
32:             return
33:                 NumberOfPartitions(number - 1, maxSummand - 1) +
34:                 NumberOfPartitions(number - maxSummand, maxSummand);
35:         }
36:     }
37: 
38:     public static PartitionSet Calculate(int number)
39:     {
40:         PartitionSet result = new PartitionSet(number);
41: 
42:         if (number == 1)
43:         {
44:             Partition p = new Partition(new int[] { 1 });
45:             result.Insert(p);
46:         }
47:         else
48:         {
49:             PartitionSet setMinusOne = Calculate(number - 1);
50: 
51:             for (int i = 0; i < setMinusOne.Count; i++)
52:             {
53:                 int[] numbers = setMinusOne[i].Numbers;
54: 
55:                 for (int j = 0; j < numbers.Length; j++)
56:                 {
57:                     numbers[j]++;
58:                     Partition p = new Partition(numbers);
59:                     result.Insert(p);
60:                     numbers[j]--;
61:                 }
62:             }
63: 
64:             // create missing partition (just consisting of '1's)
65:             int[] partitionOnes = new int[number];
66:             for (int k = 0; k < partitionOnes.Length; k++)
67:                 partitionOnes[k] = 1;
68: 
69:             Partition pOnes = new Partition(partitionOnes);
70:             result.Insert(pOnes);
71:         }
72:         return result;
73:     }
74: }

Beispiel 3. Klasse PartitionsCalculator.