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 Fallstudie. Als Elemente verwenden wir zunächst Zeichen, also char-Variablen. Dies soll aber verallgemeinerbar sein, also auch für Variablen eines beliebigen Datentyps funktionieren.

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).

Lernziele

• Template-Technik
• STL-Container std::vector<T> und std::list<T>
• STL-Algorithmen std::for_each, std::begin, std::end, std::rbegin und std::rend
• STL-Iteratoren
• Lambda-Funktionen mit Zugriffsklausel
• Initialisierungsliste (std::initializer_list<T>)
• Anwendungsbeispiel für std::move
• Anwendungsbeispiel für std::next_permutation
• Benutzerdefinierter Literaloperator (operator"")
• Bereichsbasierte for-Wiederholungsschleife (Range-based for-Loop)

Einführung

Bevor wir auf den Algorithmus zur Berechnung von Permutationen eingehen, entwickeln wir zwei Hilfsklassen Permutation und PermutationContainer. Da wir für die Permutationen unterschiedliche Datentypen der einzelnen Elemente zu Grunde legen wollen, kommen bei der Realisierung Klassen-Templates ins Spiel.

Klasse Permutation<T>

Die Klasse Permutation – genauer: Permutation<T> – benötigen wir, um eine einzelne Permutation darzustellen. Überlegen Sie, welcher Container der STL als Hilfestellung dafür geeignet sein könnte? Die Details zur Schnittstelle des Klassen-Templates Permutation<T> sind in Tabelle 1 zusammengestellt:

Tabelle 1: Element der Klasse Permutation<T>.

Natürlich wäre es auch wünschenswert, wenn man ein Permutation<T>-Objekt mit dem operator<< auf der Konsole ausgeben kann:

std::ostream& operator<< (std::ostream&, const Permutation<T>&);

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

Permutation<char> p{ 'A', 'B', 'C' };
std::cout << p << std::endl;

Ausgabe:

[A,B,C]

Noch ein ähnliches Beispiel mit den fünf Zahlen 1, 2, 3, 4 und 5:

Permutation p{ 1, 2, 3, 4, 5 };
std::cout << p << " (Anzahl der Elemente: " << p.grade() << ')' << std::endl;

Ausgabe:

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

Man beachte im letzten Beispiel, dass der Template Parametertyp T – in diesem Beispiel int – vom Übersetzer aus dem Datentyp der Parameter abgeleitet werden kann. Es folgt noch ein Beispiel zu den Methoden insertAtFront, removeAt und dem Index-Operator oeprator[]:

Permutation p{ 1, 2, 3, 4, 5 };

std::cout << "Testing insertAtFront: " << std::endl;
p.insertAtFront(0);
std::cout << p << std::endl;

std::cout << "Testing []-Operator: " << std::endl;
for (size_t i{}; i != p.grade(); ++i)
{
    int n = p[i];
    std::cout << i << ": " << n << std::endl;
}

std::cout << "Testing removeAt: " << std::endl;
do
{
    p = p.removeAt(0);
    std::cout << p << std::endl;
}
while (p.grade() != 0);

Ausgabe:

Testing insertAtFront:
[0,1,2,3,4,5]
Testing []-Operator:
0: 0
1: 1
2: 2
3: 3
4: 4
5: 5
Testing removeAt:
[1,2,3,4,5]
[2,3,4,5]
[3,4,5]
[4,5]
[5]
[]

Klasse PermutationContainer<T>

Zum Abspeichern mehrerer Permutation<T>-Objekte konzipieren wir eine Klasse PermutationContainer<T>. Im Prinzip handelt es sich bei dieser Klasse um eine Hüllenklasse, die einen geeignet auszuwählenden STL-Container für eine beliebige Anzahl von Permutation<T>-Objekten kapselt. Eine derartige Hüllenklasse ergibt Sinn, da wir neben den Standard-Methoden des STL-Containers noch einige zusätzliche Hilfsmethoden benötigen, die speziell auf den Algorithmus zur Berechnung von Permutationen zugeschnitten sind. Damit werfen wir einen Blick auf Tabelle 2:

Tabelle 2: Element der Klasse PermutationContainer<T>.

Auch sollte der operator<< für PermutationContainer<T>-Objekte realisiert sein, um ein derartiges Container-Objekt auf der Konsole ausgeben zu können:

std::ostream& operator<< (std::ostream&, const PermutationContainer<T>&);

Ein Beispiel zur PermutationContainer<T>-Klasse könnte so aussehen:

Permutation<int> p{ 1, 2, 3, 4 };
Permutation<int> q{ 4, 3, 2, 1 };
std::cout << p << std::endl;
std::cout << q << std::endl;

PermutationContainer<int> container{};
container.insert(p);
container.insert(q);
std::cout << container << std::endl;

Ausgabe:

[1,2,3,4]
[4,3,2,1]
[1,2,3,4]
[4,3,2,1]
[2 permutations]

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:

• Erster Fall: n = 1
  Die Menge hat nur ein Element, nennen wir es a₁. Es existiert in diesem Fall nur eine einzige Permutation, bestehend aus dem Element a₁.

• Zweiter Fall: n > 1
  Wir bezeichnen die Elemente mit a₁, a₂, a₃, … , a_n-1, a_n: Nun ist der Reihe nach jedes einzelne Element a_i (i = 1,2, …, n) vorü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 insertAtFront-Methode aus Tabelle 1.

Wir demonstrieren in Abbildung 1 die Funktionsweise dieses Algorithmus am Beispiel einer Permutation mit den drei Ziffern 1, 2 und 3:

Abbildung 1: Rekursiver Algorithmus zur Bestimung von Permutationen.

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

[caption=“Abbildung {counter:figure}: “, title=“Pseudo-Code der Methode calculate."] image::PermutationPseudeCode.png[width=450]

Abbildung 2: Algorithmus zur Berechnung von Permutationen.

Wir sind fast am Ziel angekommen: Die im letzen Abschnitt beschriebene Methode calculate ordnen wir der Klasse PermutationCalculator<T> zu:

Klasse PermutationCalculator<T>

Die Definition in Tabelle 3 stellt im Prinzip nur eine Wiederholung dar:

Tabelle 3: Methode calculate der Klasse PermutationCalculator<T>.

Nachfolgend ein Beispiel, wie Sie das Klassen-Template PermutationCalculator<T> zur Berechnung von Permutationen einsetzen können:

Permutation<char> p{ 'A', 'B', 'C' };
PermutationContainer<char> result = PermutationCalculator<char>::calculate(p);
std::cout << result << std::endl;

Ausgabe:

[A,B,C]
[A,C,B]
[B,A,C]
[B,C,A]
[C,A,B]
[C,B,A]
[6 permutations]

Aufzählung von Permutationen

Für den Anwender ist häufig – vor allem bei größeren Datenmengen – das einzelne Aufzählen der Daten komfortabler. Ergänzen Sie deshalb das Klassen-Template PermutationContainer<T> um die Realisierung einer Aufzählungsschnittstelle.

In C++ ist das Aufzählen einer Menge von Werten im Prinzip durch das STL-Iteratorenkonzept bereits vorgegeben. Je nachdem, in welcher C++–Stilistik Sie programmieren wollen, lässt sich das Ergebnis einer Permutationen-Berechnung mit dem STL-Algorithmus std::for_each oder einer so genannten Range-based for Loop ausgeben. Wir betrachten beide Varianten an einem Beispiel:

Permutation<int> p{ 1, 2, 3 };
PermutationContainer<int> result = PermutationCalculator<int>::calculate(p);

for (const auto& perm : result) {
    std::cout << "Next Permutation: " << perm << std::endl;
}

oder

Permutation<int> p{ 1, 2, 3 };
PermutationContainer<int> result = PermutationCalculator<int>::calculate(p);

std::for_each(
    std::begin(result),
    std::end(result),
    [](const auto& perm){
        std::cout << "Next Permutation: " << perm << std::endl;
    }
);

In beiden Fällen sollten wir die gleiche Ausgabe erhalten:

Next Permutation: [1,2,3]
Next Permutation: [1,3,2]
Next Permutation: [2,1,3]
Next Permutation: [2,3,1]
Next Permutation: [3,1,2]
Next Permutation: [3,2,1]

Literale für Permutationen

Mit dem C++–Feature User defined Literal lassen sich Permutations-Objekte auch als Konstante formulieren:

Permutation<int> p { 12345_perm };

Realisieren Sie den Literal-Operator für die Klasse Permutation<int> mit dem Suffix _perm. Testen Sie Ihre Realisierung an folgendem Beispiel:

PermutationContainer<int> container
{ 
    123_perm, 132_perm, 213_perm, 231_perm, 312_perm,321_perm
};

for (const auto& perm : container) {
    std::cout << "Permutation: " << perm << std::endl;
}

Ausgabe:

Permutation: [1,2,3]
Permutation: [1,3,2]
Permutation: [2,1,3]
Permutation: [2,3,1]
Permutation: [3,1,2]
Permutation: [3,2,1]

Lösung

Quellcode: Siehe auch Github.

Klassen-Template Permutation<T>

Kommen wir jetzt auf das Klassen-Template Permutation<T> zu sprechen. Wir realisieren alle Templates in dieser Fallstudie nach dem so genannten Inclusion Modellprinzip, das heißt, wir fügen die Realisierung der Methoden in der Header-Datei mit ein (Listing 1):

01: template <typename T>
02: class Permutation
03: {
04: private:
05:     std::vector<T> m_values;
06: 
07: public:
08:     // c'tors
09:     Permutation() = default;
10:     Permutation(std::initializer_list<T> list) : m_values{ list } {}
11: 
12:     // getter
13:     size_t grade() const { return m_values.size(); }
14: 
15:     // public interface
16:     void insertAtFront(T elem) {
17:         m_values.insert(m_values.begin(), elem);
18:     }
19: 
20:     Permutation<T> removeAt(size_t idx) const {
21:         std::vector<T> tmp{ m_values };
22:         tmp.erase(tmp.begin() + idx);
23:         return { std::move(tmp) };
24:     }
25: 
26:     std::vector<T> getValues() const { return m_values; }
27: 
28:     // operator(s)
29:     const T& operator[](size_t n) const {
30:         return m_values[n];
31:     };
32: 
33:     // iterator support
34:     typename std::vector<T>::const_iterator begin() { return m_values.begin(); }
35:     typename std::vector<T>::const_iterator end() { return m_values.end(); }
36: 
37: private:
38:     Permutation(std::vector<T>&& values) noexcept : m_values{ std::move(values) } {}
39: };

Listing 1: Klassen-Template Permutation<T>.

Einige Anweisungen in Listing 1 sollten wir näher betrachten:

• Zeilen 20 bis 24 – Das Entfernen eines Elements einer Permution soll in einem neuen Permutation<T>-Objekt abgelegt werden. Hierzu wird in Zeile 21 ein temporäres std::vector<T>-Objekt benötigt. Dieses soll mit der Verschiebe-Semantik in ein neues Permutation<T>-Objekt verschoben werden. Dazu haben wir in Zeile 38 einen passenden Verschiebe-Konstruktor definiert.
• Zeile 26 – Die getValues-Methode benötigen wir, wenn wir die calculate-Methode mit dem STL-Algorithmus std::next_permutation implementieren.
• Zeilen 34 und 35 – Die Aufzählungsschnittstelle des Klassen-Templates Permutation<T> kann einfach dadurch realisiert werden, indem das Iterieren auf ein unterlagertes STL-Containerobjekt durchgereicht wird. In unserem Beispiel bedienen wir uns hierzu der Iteratorschnittstelle des std::vector<T>-Objekts aus Zeile 5.

Klassen-Template PermutationContainer<T>

01: template <typename T>
02: class PermutationContainer
03: {
04: private:
05:     std::list<Permutation<T>> m_perms;
06: 
07: public:
08:     // c'tors/d'tor
09:     PermutationContainer() = default;
10:     PermutationContainer(std::initializer_list<Permutation<T>> perms) : m_perms{ perms } {}
11: 
12:     // getter
13:     size_t count() const { return m_perms.size(); }
14: 
15:     // public interface
16:     void insert(const Permutation<T>& p) {
17:         m_perms.push_back(p);
18:     }
19: 
20:     void insertAll(T elem) {
21:         for (Permutation<T>& p : m_perms) {
22:             p.insertAtFront(elem);
23:         }
24:     }
25: 
26:     // iterator support
27:     typename std::list<Permutation<T>>::iterator begin() { return m_perms.begin(); }
28:     typename std::list<Permutation<T>>::iterator end() { return m_perms.end(); }
29:     typename std::list<Permutation<T>>::const_iterator begin() const { return m_perms.cbegin(); }
30:     typename std::list<Permutation<T>>::const_iterator end() const { return m_perms.cend(); }
31: };

Listing 2: Klassen-Template PermutationContainer<T>.

Wir fahren nahtlos mit der Klasse PermutationCalculator<T> fort:

Klassen-Template PermutationCalculator<T>

01: template <typename T>
02: class PermutationCalculator
03: {
04: public:
05:     // public interface
06:     static PermutationContainer<T> calculate(const Permutation<T>& p) {
07:         if (p.grade() == 1)
08:         {
09:             PermutationContainer<T> a{};
10:             a.insert(p);
11:             return a;
12:         }
13:         else
14:         {
15:             PermutationContainer<T> result{};
16: 
17:             for (size_t i{}; i != p.grade(); ++i)
18:             {
19:                 // create permutation without i.-th element of current permutation
20:                 Permutation<T> q{ p.removeAt(i) };
21: 
22:                 // calculate permutions of n-1 elements recursively
23:                 PermutationContainer<T> perms{ PermutationCalculator::calculate(q) };
24: 
25:                 // join result with removed character
26:                 perms.insertAll(p[i]);
27: 
28:                 // append calculated permutations
29:                 for (const auto& perm : perms) {
30:                     result.insert(perm);
31:                 }
32:             }
33: 
34:             return result;
35:         }
36:     }
37: 
38:     static PermutationContainer<T> calculateEx(const Permutation<T>& p) {
39: 
40:         PermutationContainer<T> result{};
41: 
42:         // retrieve std::vector with values from permutation
43:         std::vector<T> values = p.getValues();
44: 
45:         // values need to be sorted
46:         std::sort(
47:             std::begin(values),
48:             std::end(values)
49:         );
50: 
51:         // keep calculating next permutation while there is a next permutation
52:         do {
53:             Permutation<T> tmp{};
54: 
55:             std::for_each(
56:                 std::rbegin(values),
57:                 std::rend(values),
58:                 [&](const auto& elem) { 
59:                     tmp.insertAtFront(elem);
60:             });
61: 
62:             result.insert(tmp);
63: 
64:         } while (std::next_permutation(std::begin(values), std::end(values)));
65: 
66:         return result;
67:     }
68: };

Listing 3: Klassen-Template PermutationCalculator<T>.

Es fehlt noch die Realisierung des Literal-Operators operator"":

Literale für Permutationen

01: Permutation<int> operator"" _perm(unsigned long long int value) {
02: 
03:     Permutation<int> p;
04: 
05:     while (value != 0) {
06: 
07:         int rest{ static_cast<int>(value % 10) };
08:         p.insertAtFront(rest);
09:         value = value / 10;
10:     }
11: 
12:     return p;
13: }

Listing 4: Literal-Operator operator"" für das Suffix _perm.

There‘s more

Vermutlich sind Sie schon einmal über das Akronym DRY gestolpert: Don’t Repeat Yourself: Im Software Engineering bezeichnet man damit ein Prinzip, das besagt, Redundanzen zu vermeiden oder zumindest zu reduzieren. Es handelt sich hierbei auch um ein Prinzip von Clean Code.

Hätten wir die Betrachtung der Permutationen in dieser Fallstudie nicht zum Zwecke des Übens gemacht, müssten wir uns eingestehen, dass eine derartige Realisierung in der STL bereits vorhanden ist:

std::next_permutation

Ergänzen Sie Ihre Realisierung des Klassen-Template PermutationCalculator<T> um eine zweite Methode calculateEx, deren Realisierung den STL-Algorithmus std::next_permutation verwendet. Vergleichen Sie die Resultate der beiden Realisierungen.

See also

• Rechtwinklige Dreiecke und parallel_for
• Kettenrechnen
• Variadisch + Generisch = Folding + Rekursion: Wie bitte?
• Das Problem der dinierenden Philosophen
• Fakultäten, Binomialkoeffizienten und Herr Legendre