Einführung

Unter einer Permutation versteht man in der Mathematik die Veränderung der Reihenfolge der Elemente einer Menge. Zum Beispiel kann die Permutation eines bestimmten strings bei der Suche nach einem Passwort, wessen Buchstaben zwar bekannt sind nicht aber deren Reihenfolge, ganz nützlich sein.

Eine Permutation ist mathematisch gesehen eine bijektive Abbildung einer endlichen Menge mit n Elementen auf sich selbst . Es handelt sich daher einfach um eine Neuanaordnung der Elemente. Als solche ist sie eineindeutig und es existiert somit eine Umkehrfunktion. Das bedeutet nichts anderes als das sie aus der Zielmenge wieder eindeutig auf die Bildmenge schließen können.

Permutationen spielen nicht nur in der reinen Kombinatorik eine wichtige Rolle sondern finden auch in der Spieleentwicklung Verwendung. Darunter zum Beipiel bei der Matrizenberechnung von geometrischen Figuren.

Permutation ohne Wiederholung

Bei der Permutation ohne Wiederholung müssen folgende Voraussetzungen erfüllt sein:

• Alle (N) Elemente der Ausgangsmenge unterscheiden sich voneinander.
• Es müssen alle (N) Elemente ausgewählt werden.
• Ein Element kann nicht mehrmals ausgewählt werden.

Die Berechnung erfolgt über die Fakultätsbildung , wobei n stellvetretend für die Anzahl der Elemente steht. Es gilt . Falls ihnen der Begriff der Fakultät nicht geläufig ist, so können sie anhand der nachfolgenden Formel ersehen wie diese gebildet wird.

Nehmen wir als Beispiel die folgende Situation an. Ein Einbrecher benötigt zum Öffnen einer durch ein Kombinationsschloß verriegelten Türe einen Code. Nach gründlicher Spurensuche findet er heraus, das sich auf dem Schloss nur auf vier Tasten Fingerabdrücke befinden. Nämlich auf Taste 3, 4, 5 und 8. Außerdem weiß er das beim Codeschloß mit der Seriennummer 25F7-ST66 ein 4-stelliger Zugangscode in der richtigen Reihenfolge eingegeben werden muss. Die Frage lautet nun, wieviele Kombinationen muss unser Einbrecher durchgehen um das Schloß zu knacken und welche sind das?

Wie bereits oben erläutert errechnet sich die Anzahl der möglichen Kombinationen aus der Fakultät. Somit ergeben sich für vier unterschiedliche Elemente aus der Menge P insgesamt 24 Permutationen. Nachfolgend sind diese vollständig gelistet: 3458, 3485, 3548, 3584, 3845, 3854, 4358, 4385, 4538, 4583, 4835, 4853, 5348, 5384, 5438, 5483, 5834, 5843, 8345, 8354, 8435, 8453, 8534, 8543.

Nun ist das Ganze für vier Zahlen (Elemente) noch sehr überschaubar und die 24 verschiedenen Permutationen lassen sich problemlos in kurzer Zeit durchdenken. Doch aufgrund des Wachstumsverhaltens von n! steigt die Anzahl an möglichen Permutationen ab 5 Elementen sehr stark an und erreicht bereits für n=69 eine Zahl mit unglaublichen 99 Dezimalstellen! Deshalb wäre es gut ein Programm zu haben welches uns die Aufgabe der Berechnung abnimmt. Die C++ Standard Bibliothek mit ihren mächtigen Algorithmen stellt uns hierfür die Funktionen prev_permutation und next_permutation zur Verfügung. Diese sind in der STD Header-Datei algorithm versammelt. Der Algorithmus prev_permutation generiert für den Bereich [first, last] alle vorhergehenden Permutation der Elemente, während next_permutation dies für alle nachfolgenden macht.

Geordnete Elemente

Beachten sie das der STL Algorithmus davon ausgeht dass alle Elemente lexikographisch geordnet vorliegen! Existiert eine vor-/nachfolgende Permutation wird true zurückgegeben. Das untere Programm erzeugt für die Buchstaben A, B und C insgesamt sechs Permutationen.

// Calculate Permutations - using STL Algorithms
#include <iostream>
#include <algorithm>
 
int main()
{
    char f[] = { 'A', 'B', 'C' }, *const fn = f + sizeof(f) / sizeof(*f);
    unsigned int i = 0;
 
    do
    {
        std::cout << ++i << ". Permutation: ";
        copy(f, fn, std::ostream_iterator<char>(std::cout, " "));
        std::cout << std::endl;
    }
    while(std::next_permutation(f, fn));
 
    return 0;
}

Der Algorithmus aus der STL generiert alle nachfolgenden Permutationen für die Elemente A, B, und C die in Frage kommen und gibt diese auf den Bildschirm aus.

Ungeordnete Elemente

Wie lässt sich der Algorithmus nun auch bei lexikographisch ungeordneten Wörtern (Elementen), wie z.B. monkey verwenden? Vielleicht können sie es sich schon denken!? Wir müssen den string einfach nur ordnen lassen bevor wir diesen an die STL Funktion übergeben.

Wir benutzen dafür die STL Funktion stable_sort(). Im Durchschnitt ist die auf Qicksort basierende sort() Funktion zwar etwas schneller, kann aber unter Umständen das Laufzeitverhalten des Programms negativ beeinflußen. Werfen wir nun einmal einen Blick auf die veränderte Funktion mit dem neuen Namen SSTL_Permutation:

// ============================================================================
// Function:    SSTL_Permutation
// Description: Generate all permuted strings for an input string using
//              original STL function next_permutation().
// Parameter:   @input: the input string.
//              @result: the buffer, where permutations are stored
// Note:        STL next_permutation permutes the string input to the 
//              lexicographically next string as an arrangement, and then 
//              returns true. Due to this reason, the STL function stable_sort
//              is called before.
// ============================================================================
void SSTL_Permutation(const std::string& input, std::vector<std::string>& result)
{
    std::string cs(input);
 
    std::stable_sort(cs.begin(), cs.end()); 
 
    do   
        result.push_back(cs);
    while(std::next_permutation(cs.begin(), cs.end())); 
}

Wir haben der Funktion eine Containerklasse des Typs std::vector mit den Vektorelementen std::string spendiert. Dieser Container soll unsere generierten Permutationen aufnehmen und verwalten. Er wird als Parameter an die Funktion übergeben. Vor Aufruf der Funktion lässt sich ausreichend Speicherplatz für den Container allokieren, was die Berechnung beschleunigt.

Nehmen Sie zur Kenntnis das ein Container der Standard Template Library den Speicher dynamisch verwaltet und die Größe eines vectors begrenzt ist.

Die Speicherallokation mit reserve() scheitert, falls die maximale Grenze max_size() überschritten wird. In dem Fall wird eine Ausnahme des Typs length_error oder sogar bad_alloc geworfen. Da die Fakultät ein hohes Wachstum aufweist ist die Größe eines Containers bei zu großen Werten von n nicht mehr ausreichend um die Menge an Daten im flüchtigen Speicher aufzubewahren. Die maximale Größe eines vector liegt auf meinem System, bei 134217727 Elementen. Diese Anzahl wird bei mehr als 11 unterschiedlichen Elementen der Ausgangsmenge bereits überschritten. Verwenden Sie in dem Fall eine Variante der Funktion SSTL_Permutation, die ein Objekt vom Typ ofstream als Parameter entgegennimmt und die Permutationen direkt in einer persistenten Datei ablegt, ohne die Werte zwischenzuspeichern.

In der oben aufgeführten Funktion erzeugt die do while() Schleife alle Permutationen und fügt diese in den vector ein. Nun werden auch lexikographisch unsortierte strings korrekt verarbeitet.

Eine weitere Möglichkeit dieses Ziel zu erreichen besteht darin die Standard STL Funktion next_permutation neu zu implementieren, so dass diese auch mit unsortierten strings umgehen kann. Sehen sie sich dazu einfach mal die folgende Implementierung, samt der aufrufenden Funktion ISTL_Permutation an.

#include <map>
#include <string>
#include <vector>
#include <algorithm>
 
// generate associative container pair key
typedef std::map<char, size_t> POSITION_MAP;
 
// STL: Extended TEMPLATE FUNCTION _next_permutation from algorithm standard header
// permute and test for pure ascending, using operator<
template<class _BidIt> inline
bool _next_permutation(_BidIt _First, _BidIt _Last, POSITION_MAP *pMap/*default=NULL*/)
{   
    _BidIt _Next = _Last;
    if (_First ==_Last || _First == --_Next) return false;
 
    for (; ; ) {   
        _BidIt _Next1 = _Next;
        if (pMap? (*pMap)[*--_Next] < (*pMap)[*_Next1]: *--_Next < *_Next1) {   
            _BidIt _Mid = _Last;
            for (; !(pMap? (*pMap)[*_Next] < (*pMap)[*--_Mid]: *_Next < *--_Mid);)
                ; 
 
            std::iter_swap(_Next, _Mid);
            std::reverse(_Next1, _Last);   
            return true;
        }
 
        if (_Next == _First) {   
            std::reverse(_First, _Last);
            return false;
        }
    }
}
 
// ============================================================================
// Function:    ISTL_Permutation
// Description: Generate all permuted strings for an input string using
//              extended STL function _next_permutation().
// Parameter:   @input: the input string.
//              @result: the buffer, where permutations are stored
//              @bOrdered: flag to set optionally ordering On/Off.
// Note:        STL next_permutation permutes the string input to the 
//              lexicographically next string as an arrangement, and then 
//              returns true. If the string is in descending order then 
//              it returns false.
// ============================================================================
void ISTL_Permutation(const std::string& input, std::vector<std::string>& result, 
                      bool bOrdered)
{
    POSITION_MAP mapPos;
    std::string cs(input);
 
    if(!bOrdered)   /*default=true*/
        for(size_t i = 0; i < cs.length(); i++)
            mapPos.insert(std::pair<char, unsigned int>(cs[i], i));   
 
    do   
        result.push_back(cs);   
    while(_next_permutation(cs.begin(), cs.end(), bOrdered ? NULL : &mapPos)); 
}

Sicherlich erscheint Ihnen diese Lösung etwas umständlicher und ineffizienter. Aber sie ist performancetechnisch der oberen Funktion ungefähr gleichzusetzen. Bis auf die Tatsache das sie aufgrund der Neuimplementierung von next_permutation etwas länger ausfällt. Wie sie nun wahrscheinlich schon erkannt haben, nennen wir diese neue Funktion _next_permutation. Es handelt sich im Prinzip um den originalen STL Algorithmus der ledeglich ein klein wenig modifiziert wurde. Die Funktion ISTL_Permutation() nimmt insgesamt zwei Parameter auf. Zum Einen den input string und zum Anderen das Flag bOrdered, welches es der Funktion ermöglichen soll auch lexikographisch ungeordnete strings in allen Kombinationen auszugeben.

Im Default Modus ist das Flag true und die Template Funktion _next_permutation verhält sich wie die Standard-Implementierung aus der STL. Wird allerdings explizit false übergeben, generiert die Funktion auch für unsortierte input strings alle Permutationen.

Dazu wird der Code um einen assoziativen Container der Klasse map erweitert. Die Klasse map verwaltet Paare von Schlüsseln und Werten. Mit Hilfe des Schlüssels kann dann eindeutig auf den zugeordneten Wert zugegriffen werden. Der mit typedef vereinbarte Name vereinfacht die spätere Benutzung, ähnlich wie sie es z.B. sicherlich schon von C-Structs her kennen.

Sobald das Flag bOrdered false ist (string ist also unsortiert), wird die if() Bedingung ausgeführt und ein Schlüsselpaar, ein sogenanntes pair-key, bestehend aus einem char und einem unsigned int angelegt und in das map-Objekt eingefügt. Im char wird der Buchstabe und im unsigned int dessen Position im string gespeichert. Dieses Paar wird anschließend an _next_permutation() übergeben. Dort führt (*pMap)[*i]<(*pMap)[*j] einen Sortierungsvergleich aus und liefert alle Permutationen zurück. Fertig ist die erweiterte STL Funktion.