Permutationen

1. Aufgabe

Ist eine Menge von n Elementen gegeben, so bezeichnet man die möglichen Anordnungen aller dieser n Elemente als Permutationen (lat. permutare: vertauschen). Die Berechnung der Permutationen einer beliebigen Menge von Elementen steht im Mittelpunkt dieser Aufgabe. Als Elemente verwenden wir Zeichen, also char-Variablen.

Für zwei Zeichen A und B gibt es nur die zwei Permutationen AB und BA. Drei Zeichen, angenommen A, B und C, können hingegen in sechs verschiedenen Permutationen dargestellt werden: ABC, ACB, BAC, BCA, CAB und CBA. Sind alle n Elemente voneinander verschieden, was wir in dieser Aufgabe zu Grunde legen, so gibt es dafür n! Anordnungen (n-Fakultät).

Bevor wir auf den Algorithmus zur Berechnung von Permutationen eingehen, entwickeln wir zwei Hilfsklassen Permutation und PermutationArray.

1.1. Klasse Permutation

Die Klasse Permutation benötigen wir, um eine einzelne Permutation darzustellen. Im wesentlichen bestehen Permutation-Objekte aus zwei Instanzvariablen: Einem flexibel langen Array, das die Zeichen der Permutation beschreibt (Instanzvariable m_values) und einer weiteren Instanzvariablen m_length, die die Länge des Zeichenarrays enthält (Abbildung 1):

Struktur eines Permutation-Objekts.

Abbildung 1. Struktur eines Permutation-Objekts.


Weitere Details zur Schnittstelle der Klasse Permutation sind in Tabelle 1 zusammengestellt.

Element

Beschreibung

Konstruktor

Permutation ();

Der Standardkonstruktor initialisiert ein leeres Permutation-Objekt: Es enthält keine Zeichen und die Anzahl der Zeichen ist dementsprechend 0.

Konstruktor

Permutation (char values[], int length);

Initialisiert ein Permutation-Objekt mit einer Reihe von Zeichen (char-Variablen), die in dem Array values abgelegt sind. Die Länge des Arrays wird durch den zweiten Parameter length spezifiziert. Sinnvollerweise sollten die Zeichen in dem Array alle voneinander verschieden sein. Sie brauchen das in Ihrer Implementierung aber nicht zu überprüfen.

getter-Methode Grade

int Grade ();

Liefert die Anzahl der char-Elemente zurück, die im Objekt abgelegt sind. Man spricht auch von der Länge bzw. vom Grad der Permutation.

Methode Insert

void Insert (char c);

Die Insert-Methode verändert die aktuelle Permutation wie folgt: Das übergebene Zeichen c wird in der vorliegenden Permutation am Anfang eingefügt. Inbesondere wird der Grad der Permutation damit um Eins größer.

Hinweis: Die Insert-Methode benötigen wir für den Algorithmus zur Berechnung von Permutationen!

Methode Remove

Permutation Remove (int i);

Die Remove-Methode erzeugt eine neue Permutation, die aus der aktuellen Permutation durch Entfernen des i.-ten Zeichens entsteht. Die vorliegende Permutation bleibt unverändert. Der Grad der neuen Permutation ist folglich um Eins kleiner als der Grad der aktuellen Permutation.

Hinweis: Die Remove-Methode benötigen wir für den Algorithmus zur Berechnung von Permutationen!

Operator []

char operator[] (int i);

Liefert das i.-te Zeichen der Permutation zurück.

Operator <<

ostream& operator<< (ostream& os, const Permutation& p);

Gibt ein Permutation-Objekt auf der Konsole aus. Die einzelnen Zeichen der Permutation sind durch Komma voneinander zu trennen, die Permutation selbst ist in eckige Klammern [ und ] zu setzen.

Tabelle 1. Wesentliche Elemente der Klasse Permutation.


Es folgen einige Beispiele, um die Arbeitsweise der Klasse Permutation zu verdeutlichen. Eine Permutation mit den drei Zeichen C, B und A wird so angelegt:

Permutation p ("CBA", 3);
cout << p << endl;

Ausgabe:

[C,B,A]

Noch ein ähnliches Beispiel mit einer Permutation der fünf Ziffern 1, 2, 3, 4 und 5:

Permutation p ("12345", 5);
cout << p << " (Anzahl der Elemente: " << p.Grade() << ')' << endl;

Ausgabe:

[1,2,3,4,5] (Anzahl der Elemente: 5)

Ein Beispiel zur Grade-Methode und dem []-Operator könnte so aussehen:

Permutation p ("ABC", 3);
for (int i = 0; i < p.Grade(); i ++)
{
    char c = p[i];
    cout << i << ": " << c << endl;
}

Ausgabe:

0: A
1: B
2: C

Wir schließen mit einem Beispiel zur Insert-Methode ab:

Permutation p ("ABC", 3);
cout << p << " (Grad: " << p.Grade() << ')' << endl;
p.Insert ('D');
cout << p << " (Grad: " << p.Grade() << ')' << endl;

Ausgabe:

[A,B,C] (Grad: 3)
[D,A,B,C] (Grad: 4)

1.2. Klasse PermutationArray

Zum Abspeichern mehrerer Permutation-Objekte konzipieren wir eine Klasse PermutationArray. PermutationArray-Objekte sind vor allem dann hilfreich, wenn während der Berechnung der Permutationen bereits eine (unvollständige) Menge an Permutation-Objekten vorliegt.

Die Anzahl der Permutationen, die in einem PermutationArray-Objekt abzulegen sind, steht immer im vornehinein fest. Es ist also nicht erforderlich, die Implementierung der PermutationArray-Klasse für eine flexible Anzahl von Permutation-Objekten auszulegen. Diese Aussage legen wir beim Betrachten von Abbildung 2 zu Grunde, die ein PermutationArray-Objekt zeigt, das Platz für fünf Permutationen besitzt. Die ersten drei Permutation-Objekte sind bereits eingetragen (erkennt man an der Instanzvariablen m_length, die im Beispiel den Wert 7 besitzt). Die letzten zwei Permutation-Objekte sind leer, die Werte der Instanzvariablen sind entsprechend gewählt.

Struktur eines PermutationArray-Objekts.

Abbildung 2. Struktur eines PermutationArray-Objekts.


PermutationArray-Objekte bestehen in Abbildung 2 aus drei Instanzvariablen: Der Instanzvariablen m_array, die auf ein Array von Permutation-Objekten verweist und zwei weiteren ganzzahligen Instanzvariablen m_size und m_top: m_size spezifiziert die Länge des Arrays, m_top den Füllgrad. Der Füllgrad gibt an, bis zu welchem Index das Array mit nicht-leeren Permutation-Objekten bereits gefüllt ist. Alle weiteren Permutation-Objekte sind leer (Vorbelegung erfolgt mit Standard-Konstruktor) und können noch mit nicht-leeren Permutation-Objekten überschrieben werden.

Weitere Details zur Schnittstelle der PermutationArray-Klasse entnehmen Sie Tabelle 2:

Element

Beschreibung

Konstruktor

PermutationArray (int size);

Initialisiert ein PermutationArray-Objekt mit der vorgegebenen Anzahl size von leeren Permutation-Objekten.

getter-Methode Size

int Size ();

Liefert die Anzahl der Permutation-Objekte zurück, die im aktuellen Objekt abgelegt sind (leere und nicht-leere Permutation-Objekte zusammen gezählt).

Methode Insert

bool Insert (const Permutation& p);

Überschreibt das erste leere Permutation-Objekt mit dem durch den Parameter p übergebenen Permutation-Objekt. Der Rückgabewert gibt ab, ob noch freie Plätze im Array vorhanden waren oder nicht.

Methode InsertAll

void InsertAll (char c);

Ruft die Methode Insert an allen Permutation-Objekten im vorliegenden PermutationArray-Objekt mit dem Parameter c auf.

Operator []

Permutation operator[] (int i);

Liefert das i.-te Permutation-Objekt aus dem zu Grunde liegenden PermutationArray-Objekt zurück.

Operator <<

ostream& operator<< (ostream& os, const PermutationArray& p);

Gibt ein PermutationArray-Objekt auf der Konsole aus: Es sind alle im Array ablegten Permutationen auf der Konsole untereinander auszugeben.

Tabelle 2. Wesentliche Elemente der Klasse PermutationArray.

1.3. Algorithmus zur Berechnung von Permutationen

Nun fehlt nur noch ein Algorithmus, um zu einer gegebenen Menge von Elementen alle Permutationen zu berechnen. Ein sehr einfacher – rekursiver – Algorithmus lässt sich in Worten so beschreiben, wenn n die Anzahl der Elemente ist:

1. Fall: n = 1

Die Menge hat nur ein Element, nennen wir es a1. Es existiert in diesem Fall nur eine einzige Permutation, bestehend aus dem Element a1 selbst.

2. Fall: n > 1

Wir bezeichnen die Elemente mit a1, a2, a3, ... , an-1, an: Nun ist der Reihe nach jedes einzelne Element ai (i = 1,2, ..., n) vorrübergehend aus der vorliegenden Menge von n Zeichen zu entfernen. Die zurückbleibenden n-1 Elemente werden nun mit diesem Algorithmus (rekursiv) permutiert. Der rekursive Methodenaufruf liefert als Ergebnis eine Menge von Permutationen zurück, die alle den Grad n-1 besitzen. Das entfernte Zeichen ist nun in diese Permutationen wieder einzufügen. Die Einfügeposition spielt dabei keine Rolle, wir entscheiden uns für den Anfang, siehe dazu auch die Insert-Methode aus Tabelle 1.

Mit Hilfe der Vorarbeiten der zwei Klassen Permutation und PermutationArray (Tabelle 1 und Tabelle 2) können wir den vorgestellten Algorithmus etwas präziser formulieren: In Abbildung 3 finden Sie Pseudo-Code für eine Methode Calculate vor:

Pseudo-Code der Methode Calculate

Abbildung 3. Pseudo-Code der Methode Calculate

1.4. Klasse PermutationCalculator

Wir sind fast am Ziel angekommen: Die im letzen Abschnitt beschriebe Methode Calculate ordnen wir der Klasse PermutationCalculator zu. Die Definition in Tabelle 3 stellt im Prinzip nur eine Wiederholung dar:

Methode

Beschreibung

Calculate

PermutationArray Calculate (const Permutation& p);

Berechnet alle Permutationen zu einer vorgegebenen Menge von Zeichen, die durch die Permutation p beschrieben werden. Das Ergebnis ist in einem Objekt des Typs PermutationArray abzulegen.

Tabelle 3. Methode Calculate der Klasse PermutationCalculator.


Nachfolgend ein Beispiel, wie Sie die Klasse PermutationCalculator zur Berechnung von Permutationen einsetzen:

void main()
{
    Permutation p ("XYZ", 3);
    PermutationCalculator calc;
    PermutationArray result = calc.Calculate (p);
    cout << result << endl;
}

Ausgabe:

[X,Y,Z]
[X,Z,Y]
[Y,X,Z]
[Y,Z,X]
[Z,X,Y]
[Z,Y,X]
[6 permutations]

1.5. Aufzählung von Permutationen

Für den Anwender ist häufig – vor allem bei größeren Ergebnismengen – das einzelne Aufzählen der Ergebnisse komfortabler. Ergänzen Sie deshalb die Klasse PermutationCalculator um die Realisierung einer Aufzählungsschnittstelle, bestehend aus drei Methoden MoveNext, Current und Reset. Details zu diesen Methoden finden Sie in Tabelle 4 vor.

Beachte: Eine sinnvolle Realisierung der Aufzählungsschnittstelle müsste im Rumpf der rekursiven Methode Calculate stattfinden, um auf diese Weise zu verhindern, dass die gesamte Menge aller Permutationen auf einen Schlag berechnet wird. Dieses Unterfangen ist nicht gerade einfach und soll deshalb nicht Ziel dieser Aufgabenstellung sein. Es ist folglich in Ihrer Implementierung legitim, vor dem ersten MoveNext-Aufruf die gesamte Permutationsmenge vorab zu bestimmen. In den nachfolgenden MoveNext-Aufrufen liefern Sie die jeweilige Permutation aus dem bereits vorliegenden Ergebnisarray zurück. Bei sehr großen Ergebnismengen ist dieser Ansatz natürlich nicht empfehlenswert und führt vor allem den Sinn einer Aufzählungsschnittstelle ad absurdum!

Methode

Schnittstelle und Beschreibung

Current

Permutation Current ();

Liefert das aktuelle Element während einer Aufzählung zurück (hier: Objekt vom Typ Permutation). Beachten Sie: Mehrere, aufeinanderfolgende Aufrufe von Current liefern immer dasselbe Element zurück. Nur mit einem Aufruf von MoveNext schreitet man in der Aufzählung um ein Element weiter.

MoveNext

bool MoveNext ();

Liefert true zurück, wenn die Aufzählung noch nicht zu Ende ist, andernfalls false. Vor dem ersten Aufruf von Current muss zwingend ein Aufruf von MoveNext erfolgt sein.

Reset

void Reset ();

Mit Reset beginnt man eine Aufzählung von vorne.

Tabelle 4. Aufzählung einer Menge von Permutationen.


Studieren Sie die Arbeitsweise einer Enumeration am folgenden Codefragment. Dazu sind noch einige wenige Erweiterungen an der Klasse PermutationCalculator vorzunehmen, die allesamt aber sehr einfach und überschaubar sind:

void main()
{
    Permutation p ("ABCD", 4);
    PermutationCalculator calc;
    calc.SetPermutation (p);
    calc.Calculate ();

    calc.Reset();
    while (calc.MoveNext())
    {
        Permutation q = calc.Current();
        cout << "Next Permutation: " << q << endl;
    }
}

Ausgabe:

Next Permutation: [A,B,C,D]
Next Permutation: [A,B,D,C]
Next Permutation: [A,C,B,D]
Next Permutation: [A,C,D,B]
Next Permutation: [A,D,B,C]
Next Permutation: [A,D,C,B]
Next Permutation: [B,A,C,D]
Next Permutation: [B,A,D,C]
Next Permutation: [B,C,A,D]
Next Permutation: [B,C,D,A]
Next Permutation: [B,D,A,C]
Next Permutation: [B,D,C,A]
Next Permutation: [C,A,B,D]
Next Permutation: [C,A,D,B]
Next Permutation: [C,B,A,D]
Next Permutation: [C,B,D,A]
Next Permutation: [C,D,A,B]
Next Permutation: [C,D,B,A]
Next Permutation: [D,A,B,C]
Next Permutation: [D,A,C,B]
Next Permutation: [D,B,A,C]
Next Permutation: [D,B,C,A]
Next Permutation: [D,C,A,B]
Next Permutation: [D,C,B,A]

2. Lösung

Quellcode: Siehe auch github.com/peterloos/Cpp_Permutations.

Nachfolgend finden Sie Lösungsvorschläge für die Klassen Permutation, PermutationArray und PermutationCalculator vor:

01: class Permutation
02: {
03: private:
04:     char* m_values;
05:     int   m_length;
06: 
07: public:
08:     // c'tors / d'tor
09:     Permutation();
10:     Permutation(char[], int);
11:     Permutation(const Permutation&);
12:     ~Permutation();
13: 
14:     // getter
15:     int Grade() const { return m_length; }
16: 
17:     // public interface
18:     void Insert(char c);
19:     Permutation Remove(int i) const;
20: 
21:     // operators
22:     Permutation& operator= (const Permutation& p);
23:     char operator[] (int i) const;
24: 
25:     // output
26:     friend ostream& operator<< (ostream& os, const Permutation& p);
27: };

Beispiel 1. Klasse Permutation: Schnittstelle.


001: #include <iostream>
002: using namespace std;
003: #include "Permutation.h"
004: 
005: // c'tors / d'tor
006: Permutation::Permutation()
007: {
008:     m_values = (char*) 0;
009:     m_length = 0;
010: }
011: 
012: Permutation::Permutation(char values[], int length)
013: {
014:     m_values = new char[length];
015:     for (int i = 0; i < length; i ++)
016:         m_values[i] = values[i]; 
017:     m_length = length;
018: }
019: 
020: Permutation::Permutation(const Permutation& p)
021: {
022:     m_values = new char[p.m_length];
023:     for (int i = 0; i < p.m_length; i ++)
024:         m_values[i] = p.m_values[i]; 
025:     m_length = p.m_length;
026: }
027: 
028: Permutation::~Permutation()
029: {
030:     delete[] m_values;
031: }
032: 
033: // public interface
034: void Permutation::Insert(char c)
035: {
036:     // allocate temporary buffer
037:     char* tmp = new char[m_length + 1];
038: 
039:     // insert 'c' at first position
040:     tmp[0] = c;
041: 
042:     // copy current permutation to the end
043:     for (int i = 0; i < m_length; i++)
044:         tmp[i+1] = m_values[i];
045: 
046:     // switch to new buffer
047:     m_length ++;
048:     delete[] m_values;
049:     m_values = tmp;
050: }
051: 
052: Permutation Permutation::Remove(int i) const
053: {
054:     // allocate temporary buffer
055:     char* tmp = new char[m_length - 1];
056: 
057:     // copy current permutation without i.-th element
058:     for (int j = 0; j < i; j++)
059:         tmp[j] = m_values[j];
060:     for (int j = i + 1; j < m_length; j++)
061:         tmp[j-1] = m_values[j];
062: 
063:     return Permutation (tmp, m_length - 1);
064: }
065: 
066: // operators
067: Permutation& Permutation::operator= (const Permutation& p)
068: {
069:     if (this == &p)
070:         return *this;
071: 
072:     delete[] m_values;
073:     m_values = new char[p.m_length];
074: 
075:     for (int i = 0; i < p.m_length; i ++)
076:         m_values[i] = p.m_values[i]; 
077:     m_length = p.m_length;
078: 
079:     return *this;
080: }
081: 
082: char Permutation::operator[] (int i) const
083: {
084:     return m_values[i];
085: }
086: 
087: // output
088: ostream& operator<< (ostream& os, const Permutation& p)
089: {
090:     os << '[';
091:     for (int i = 0; i < p.m_length; i++)
092:     {
093:         os << p.m_values[i];
094:         if (i < p.m_length - 1)
095:             os << ',';
096: 
097:     }
098:     os << ']';
099:     return os;
100: }

Beispiel 2. Klasse Permutation: Implementierung.


01: class PermutationArray
02: {
03: private:
04:     int m_size;
05:     int m_top;
06:     Permutation* m_array;
07: 
08: public:
09:     // c'tors/d'tor
10:     PermutationArray();
11:     PermutationArray(int count);
12:     PermutationArray(const PermutationArray&);
13:     ~PermutationArray();
14: 
15:     // getter
16:     int Size () { return m_size; }
17: 
18:     // public interface
19:     bool Insert (const Permutation& p);
20:     void InsertAll(char c);
21: 
22:     // operators
23:     PermutationArray& operator= (const PermutationArray& p);
24:     Permutation operator[] (int i) const;
25: 
26:     // output
27:     friend ostream& operator<< (ostream& os, const PermutationArray& a);
28: };

Beispiel 3. Klasse PermutationArray: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: 
04: #include "Permutation.h"
05: #include "PermutationArray.h"
06: #include "PermutationCalculator.h"
07: 
08: // c'tors / d'tor
09: PermutationArray::PermutationArray()
10: {
11:     m_size = 0;
12:     m_top = 0;
13:     m_array = (Permutation*) 0;
14: }
15: 
16: PermutationArray::PermutationArray(int size)
17: {
18:     m_size = size;
19:     m_top = 0;
20:     m_array = new Permutation[size];
21: }
22: 
23: PermutationArray::PermutationArray(const PermutationArray& a)
24: {
25:     m_size = a.m_size;
26:     m_top = a.m_top;
27: 
28:     m_array = new Permutation[a.m_size];
29:     for (int i = 0; i < m_top; i ++)
30:         m_array[i] = a.m_array[i];
31: }
32: 
33: PermutationArray::~PermutationArray()
34: {
35:     delete[] m_array;
36: }
37: 
38: // public interface
39: bool PermutationArray::Insert (const Permutation& p)
40: {
41:     if (m_top == m_size)
42:         return false;
43: 
44:     m_array[m_top] = p;
45:     m_top ++;
46:     return true;
47: }
48: 
49: void PermutationArray::InsertAll(char c)
50: {
51:     for (int i = 0; i < m_top; i ++)
52:         m_array[i].Insert (c);
53: }
54: 
55: // operators
56: PermutationArray& PermutationArray::operator= (const PermutationArray& a)
57: {
58:     if (this == &a)
59:         return *this;
60: 
61:     delete[] m_array;
62: 
63:     m_size = a.m_size;
64:     m_top = a.m_top;
65:     m_array = new Permutation[a.m_size];
66: 
67:     for (int i = 0; i < m_top; i ++)
68:         m_array[i] = a.m_array[i];
69: 
70:     return *this;
71: }
72: 
73: Permutation PermutationArray::operator[] (int i) const
74: {
75:     return m_array[i];
76: }
77: 
78: // output
79: ostream& operator<< (ostream& os, const PermutationArray& a)
80: {
81:     for (int i = 0; i < a.m_size; i ++)
82:         os << a.m_array[i] << endl;
83: 
84:     os << '[' << a.m_top << " permutations]" << endl;
85: 
86:     return os;
87: }

Beispiel 4. Klasse PermutationArray: Implementierung.


01: class PermutationCalculator
02: {
03: private:
04:     int m_index;
05:     Permutation m_perm;
06:     PermutationArray m_array;
07: 
08: public:
09:     // c'tor
10:     PermutationCalculator();
11: 
12:     // getter/setter
13:     void SetPermutation (const Permutation&);
14:     Permutation GetPermutation ();
15: 
16:     // public interface
17:     PermutationArray Calculate(const Permutation& p);
18:     void Calculate();
19: 
20:     // enumerator interface
21:     void Reset();
22:     bool MoveNext();
23:     Permutation Current();
24: 
25: private:
26:     int Faculty(int n) const;
27: };

Beispiel 5. Klasse PermutationCalculator: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: 
04: #include "Permutation.h"
05: #include "PermutationArray.h"
06: #include "PermutationCalculator.h"
07: 
08: // c'tor
09: PermutationCalculator::PermutationCalculator() : m_array(0), m_perm()
10: {
11:     m_index = -1;
12: }
13: 
14: // getter/setter
15: void PermutationCalculator::SetPermutation(const Permutation& p)
16: {
17:     m_perm = p;
18: }
19: 
20: Permutation PermutationCalculator::GetPermutation ()
21: {
22:     return m_perm;
23: }
24: 
25: // public interface
26: void PermutationCalculator::Calculate()
27: {
28:     m_array = Calculate (m_perm);
29: }
30: 
31: PermutationArray PermutationCalculator::Calculate(const Permutation& p)
32: {
33:     if (p.Grade() == 1)
34:     {
35:         PermutationArray a(1);
36:         a.Insert (p);
37:         return a;
38:     }
39:     else
40:     {
41:         PermutationArray result (Faculty (p.Grade()));
42: 
43:         for (int i = 0; i < p.Grade(); i++)
44:         {
45:             // create permutation without i.-th element of current permutation
46:             Permutation q = p.Remove (i);
47: 
48:             // calculate permutions of n-1 elements recursively
49:             PermutationArray tmp = Calculate(q);
50: 
51:             // join result with removed character
52:             tmp.InsertAll (p[i]);
53: 
54:             // append calculated permutations
55:             for (int m = 0; m < tmp.Size(); m++)
56:                 result.Insert (tmp[m]);
57:         }
58: 
59:         return result;
60:     }
61: }
62: 
63: // enumerator interface
64: void PermutationCalculator::Reset()
65: {
66:     m_index = -1;
67: }
68: 
69: bool PermutationCalculator::MoveNext()
70: {
71:     m_index ++;
72:     if (m_index < m_array.Size())
73:     {
74:         return true;
75:     }
76:     else
77:     {
78:         Reset();
79:         return false;
80:     }
81: }
82: 
83: Permutation PermutationCalculator::Current()
84: {
85:     return m_array[m_index];
86: }
87: 
88: int PermutationCalculator::Faculty(int n) const
89: {
90:     int result = 1;
91:     for (int i = 2; i <= n; i ++)
92:         result *= i;
93: 
94:     return result;
95: }

Beispiel 6. Klasse PermutationCalculator: Implementierung.