5. [X] Permutationen

[X] Permutationen

  • ?

    GPC schrieb:

    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.

    Nur mal gerade bis hierhin gelesen... Müsste es nicht: f:X→Xf: X \rightarrow X heißen? Ist doch die selbe Menge, wenn wenn ich deine Ausführung richtig verstanden hab.

    0
  • ?

    GPC schrieb:

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

    Mir ist noch Etwas aufgefallen. Hier schreibst du garnicht, welche Berechnung erfolgt. Also schreib doch sowas, wie "Die Berechnung der Anzahl aller möglichen Permutationen erfolgt [...]"

    0
  • G

    Hi,

    bevor du die Fehler weiterhin mir anlastest 😉 , sei darauf hingewiesen, dass nicht ich der Autor des Artikels bin, sondern ihn nur stellvertretend hier poste (siehe auch die ersten paar Sätze ganz oben).

    ProgChild schrieb:

    GPC schrieb:

    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.

    Nur mal gerade bis hierhin gelesen... Müsste es nicht: f:X→Xf: X \rightarrow X heißen? Ist doch die selbe Menge, wenn wenn ich deine Ausführung richtig verstanden hab.

    ACK. Du hast Recht.

    ProgChild schrieb:

    GPC schrieb:

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

    Mir ist noch Etwas aufgefallen. Hier schreibst du garnicht, welche Berechnung erfolgt. Also schreib doch sowas, wie "Die Berechnung der Anzahl aller möglichen Permutationen erfolgt [...]"

    Hm, dachte eigentlich es wäre klar, dass es sich hier um die Berechnung der Permutation ohne Wiederholung handelt?! Steht ja schließlich direkt drübert...

    0
  • M

    Hi,
    wie sieht's hier aus? Wenn der Artikel jetzt am Mittwoch noch raus soll, muss er am besten heute noch auf [R]...

    0
  • G

    Hi,

    werde den Artikel noch zurückhalten. Aber danke der Nachfrage.

    Grüße

    Chris

    0
  • W

    GPC schrieb:

    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;
}

    Ich würde sagen, dass hier noch

    #include <iterator>

    includet werden müsste.
    Zumindest funktioniert dein Beispiel bei mir sonst nicht
    ~gcc 3.4~

    Grüße, NewProggie

    0
  • G

    Errr... yepp. Hast recht. Danke. :xmas1:

    0
  • R

    GPC schrieb:

    int nLen = strlen(input);  
//...
        for(int i=0; i<nLen; i++)
//...
                int j;
//...
            for(int i=0; i < (int)v1.size(); i++)
            {

    ohne den Artikel wirklich gelesen zu haben, sollte der Typ nicht anstelle int eher size_t oder zumindest unsigned long sein?

    0
  • G

    Jo, der ehemalige Ritter des size_t hat natürlich recht 😉

    0
  • G

    Soooo, der Artikel wäre soweit, von Rechtschreibfehlern befreit zu werden.
    Danke im Voraus 🙂

    Chris

    0
  • M

    Dieser Artikel ist eine Leihgabe von www.codeplanet.eu und wurde von StarShaper geschrieben (Original: http://www.codeplanet.eu/modules/tutorials/article.php?storyid=7&page=0). Da ich ihn kenne und ich meine Artikel bei ihm veröffentlicht habe, hat er uns im Gegenzug freundlicherweise seine Artikel zur Verfügung gestellt, damit wir sie hier veröffentlichen können.

    -------

    Dieses Tutorial stellt ein paar grundlegende C++-Funktionen zur Berechnung von Permutationen vor. Dabei wird unter anderem auch ein Vergleich zwischen den einzelnen Algorithmen illustriert, wie z.B. der aus der STL stammenden next_permutation() und einer rekursiv aufrufenden Funktion.

    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, dessen 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 f:X→Xf: X \rightarrow X. Es handelt sich daher einfach um eine Neuanordnung der Elemente. Als solche ist sie eineindeutig und es existiert somit eine Umkehrfunktion. Das bedeutet nichts anderes, als dass 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.

    Eine Berechnung erfolgt über die Fakultätsbildung , wobei n stellvertretend für die Anzahl der Elemente steht. 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 Kombinationsschloss verriegelten Türe einen Code. Nach gründlicher Spurensuche findet er heraus, dass sich auf dem Schloss nur auf vier Tasten Fingerabdrücke befinden. Nämlich auf Taste 3, 4, 5 und 8. Außerdem weiß er, dass beim Codeschloss mit der Seriennummer 25F7-ST66 ein 4-stelliger Zugangscode in der richtigen Reihenfolge eingegeben werden muss. Die Frage lautet nun, wie viele Kombinationen muss unser Einbrecher durchgehen, um das Schloss 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, dass 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 beeinflussen. 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.
// Return:      A vector of all permuted strings.
// 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.
// ============================================================================
vector<string> SSTL_Permutation(const char *input)
{
    vector<string> result;
    string cs = input;

    stable_sort(cs.begin(), cs.end());  

    do   
        result.insert(result.end(), cs);
    while(next_permutation(cs.begin(), cs.end())); 

    return result;
}

    Wir haben der Funktion einen Container (vector) vom Typ string spendiert. Dieser Container soll unsere generierten Permutationen aufnehmen und verwalten. Die do while() Schleife erzeugt 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.

    // ============================================================================
// File:        STLPermutation.cpp 
// Description: Implementation of standard STL function next_permutation
// ============================================================================
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// generate associative container pair key
typedef map<char, int> 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.
//              @bOrdered: flag to set optionally ordering On/Off.
// Return:      A vector of all permuted strings.
// 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.
// ============================================================================
vector<string> ISTL_Permutation(const char *input, bool bOrdered/*default=true*/)
{
    POSITION_MAP mapPos;
    vector<string> result;
    string cs = input;

    if(!bOrdered)
        for(unsigned int i=0; i<cs.length(); i++)
            mapPos.insert(pair<char, unsigned int>(cs[i], i));   

    do   
        result.insert(result.end(), cs);   
    while (_next_permutation(cs.begin(), cs.end(), bOrdered ? NULL : &mapPos)); 

    return result;
}

    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, dass 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 lediglich 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.

    Permutation mit Wiederholung

    Bisher haben wir nur Fälle kennengelernt, in welchen die vorliegenden Elemente im string sich nicht wiederholt haben. Zum Beispiel ABC oder 3458 oder monkey. Allerdings kann es auch sein, dass der string mehrere Elemente gleicher Art beinhaltet. ABBA ist ein Beispiel dafür. Folgende Voraussetzungen gelten für Permutationen mit Wiederholungen.

    • Mindestens 2 Elemente der Ausgangsmenge sind identisch, d.h. die Elemente der Ausgangsmenge unterscheiden sich nicht alle voneinander.
    • Es müssen alle (N) Elemente ausgewählt werden.
    • Ein Individualelement kann nicht mehrmals ausgewählt werden, ein Element mit gleicher Eigenschaft hingegen schon. Liegen z.B. 2 rote Kugeln in der Ausgangsmenge, so muss jede der beiden roten Kugeln ausgewählt werden (Wiederholung), eine dritte rote Kugel kann aber nicht ausgewählt werden.

    Berechnet wird die Anzahl an möglichen Permutationen über die Formel:

    Der zusätzlich hinzugekommene Faktor k stellt die Anzahl der Wiederholungen eines Elementes dar. Auch hier gilt .

    So existieren beim string ABBA insgesamt 6 Permuationen. Nämlich diese: AABB, ABAB, ABBA, BAAB, BABA, BBAA. Die bisher beschriebenen iterativen Funktionen reagieren unterschiedlich auf diese neue Situation. Während die Funktion SSTL_Permutation alle Permutationen korrekt berechnet, überspringt die ISTL_Permutation Implementierung 2 Permutationen und gibt nur die strings ABBA, BAAB, BABA, BBAA zurück. Hier sollte man also genau differenzieren.

    Permutation mit Hilfe von Rekursion

    Ein relativ oft gegangener Weg, Permutationen zu errechnen, ist der über die Rekursion. Der Grund hierfür liegt in der Eigenschaft der Fakultät, welche sich hierfür geradezu anbietet. Obwohl die iterative STL-Lösung in der Performance deutlich besser als die rekursive Lösung abschneidet, wollen wir auch diese hier auflisten.

    // ============================================================================
// Function:    REC_Permutation
// Description: Generate all permuted strings for an input string
//              using Recursion
// Parameter:   @input: the input string.
//              @bRepeated: flag to allow optionally element repeat.
// Return:      A vector of all permuted strings.
// ============================================================================
vector<string> REC_Permutation(const char* input, bool bRepeated)
{
    vector<string> result, v1;
    string s1;    
    char ch;
    size_t nLen = strlen(input);      

    if(nLen==1)            // Base case: Add one-char string
        result.insert(result.end(), input);      
    else                    // nLen > 1, need recursion
    {
        for(size_t i=0; i<nLen; i++)
        {
            ch = input[i];       // Extract each char as the first

            // To exclude repeated element
            if (!bRepeated)
            {
                size_t j;

                for (j=0; j<i; j++)
                    if(ch==input[j]) 
                        break;

                if (j<i) continue;   // If i==j, Not a repeated one
            }

            s1 = input;           // Copy the original string
            s1.erase(i, 1);    // Put the rest string into s1

            v1 = REC_Permutation(s1.c_str(), bRepeated); // Recursive 

            for(std::size_type i=0; i < v1.size(); i++)
            {
                s1 = ch + v1[i];   
                result.insert(result.end(), s1);   
            }
        }
    }
    return result;
}

    Die rekursive Lösung verhält sich exakt wie die Funktion SSTL_Permutation wenn das Flag bRepeated false ist. Ist es allerdings auf true gesetzt erzeugt die Funktion REC_Permutation immer alle Permutationen, unabhängig davon ob sich vereinzelte strings wiederholen oder nicht.

    Weitere Algorithmen

    Neben den bisher gezeigten Algorithmen gibt es noch einen weiteren nennenswerten, von Phillip P. Fuchs geschriebenen, Algorithmus welcher in der Geschwindigkeit und Effizienz mit dem aus der STL gleichzieht und sogar unter gewissen Umständen besser abschneidet.

    vector<string> PHIL_Permutation(const char* input)
{
    char a[32];
    strcpy(a, input);
    int N = strlen(a);		// constant index ceiling (a[N] length)
    int ax = N - 1;			// constant index ceiling (a[N] length)
    int *p = new int[N+1];  // target array and index control array
    int i, j, tmp;			// index variables and tmp for swap

    for(i = 0; i < N+1; i++)	// p[N] > 0 controls iteration and the index boundary for i
    p[i] = i;

    vector<string> result;
    result.insert(result.end(), a);      

    i = 1;   // setup first swap points to be ax-1 and ax respectively (i & j)
    while(i < N)
    {
        p[i]--;                // decrease index "weight" for i by one
        j = ax - i % 2 * p[i]; // IF i is odd then j = ax - p[i] otherwise j = ax
        i = ax - i;            // adjust i to permute tail (i < j)

        // set Scope
        {
            tmp = a[j];		// swap(a[i], a[j])
            a[j] = a[i];
            a[i] = tmp;
            result.insert(result.end(), a);      
        }

        i = 1;                 // reset index i to 1 (assumed)
        while (!p[i])          // while (p[i] == 0)
        {
            p[i] = i;           // reset p[i] zero value
            i++;                // set new index value for i (increase by one)
        } 
    } 

    delete [] p;
    return result;
}

    Benchmark

    Um die unterschiedlichen Algorithmen in ihrer Performance und Effizienz testen zu können, habe ich neben den verschiedenen Algorithmen einen Test zum Benchmarken eingebaut. Hier lässt sich deutlich der Unterschied zwischen den unterschiedlichen Algorithmen erkennen. Während die rekursive Methode generell deutlich schlechter als die anderen abschneidet, ist die Methode "STL with SORT" am schnellsten, da die Methode "Implemented STL, Ordered" eben nicht alle Permutationen berechnet. Der Algorithmus von Phillip Fuchs schneidet bei Wiederholungen geringfügig schlechter ab als die STL-Lösung. Dies liegt an der Art der Berechnung. Der Algorithmus von Phillip Fuchs geht nämlich auch bei Wiederholungen alle Permutationen durch. Liegt keine Wiederholung vor, schneidet dieser Algorithmus oft sogar besser als die STL-Lösung ab.

    Der nachfolgende Test wurde auf einem P4 mit 2,56GHz und 1024MB RAM durchgeführt.

    Das war's! Sie finden das Programm samt Quellcode mit den implementierten Algorithmen weiter unten als Visual Studio 2003.NET gepacktes Projekt vor. Die Permutationen werden in einer Textdatei gespeichert und bis zu einer Stringlänge von 5 auch visuell ausgegeben :p .

    Permutationen.zip

    0
  • J

    Wenn ich dazu was bemerken darf: es heißt wirklich eineindeutig, nicht eindeutig. Eindeutig heißt nur, dass jedem Element ein eindeutiges Element zu geordnet wird. Sozusagen dass es sich wirklich um ne Funktion handelt. Eineindeutig dagegen sichert auch, dass man aus dem zugeordneten Element wieder das ursprüngliche rekonstruieren kann, es gibt also eine Umkehrfunktion.

    edit: siehe http://de.wikipedia.org/wiki/Bijektivität

    edit2: Einen hab ich noch:

    Geordnete Elemente

    Beachten Sie, dass

    0
  • M

    Danke für die Klarstellung. 🙂
    Hab's wieder geändert.

    0
  • G

    Jow, danke euch beiden 🙂

    0
  • M

    Sorry GPC, aber dank Jester ist mir aufgefallen, dass ich "sie" (kleingeschrieben) ziemlich oft übersehen habe.
    Ich habe alles in meinen Post reineditiert, also übernimm ihn am besten noch einmal.

    0
  • G

    Kein Problem.

    0
  • G

    Dieser Artikel ist eine Leihgabe von www.codeplanet.eu und wurde von StarShaper geschrieben (Original: http://www.codeplanet.eu/modules/tutorials/article.php?storyid=7&page=0). Da ich ihn kenne und ich meine Artikel bei ihm veröffentlicht habe, hat er uns im Gegenzug freundlicherweise seine Artikel zur Verfügung gestellt, damit wir sie hier veröffentlichen können.

    -------

    Dieses Tutorial stellt ein paar grundlegende C++-Funktionen zur Berechnung von Permutationen vor. Dabei wird unter anderem auch ein Vergleich zwischen den einzelnen Algorithmen illustriert, wie z.B. der aus der STL stammenden next_permutation() und einer rekursiv aufrufenden Funktion.

    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, dessen 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 f:X→Xf: X \rightarrow X. Es handelt sich daher einfach um eine Neuanordnung der Elemente. Als solche ist sie eineindeutig und es existiert somit eine Umkehrfunktion. Das bedeutet nichts anderes, als dass 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.

    Eine Berechnung erfolgt über die Fakultätsbildung , wobei n stellvertretend für die Anzahl der Elemente steht. 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 Kombinationsschloss verriegelten Türe einen Code. Nach gründlicher Spurensuche findet er heraus, dass sich auf dem Schloss nur auf vier Tasten Fingerabdrücke befinden. Nämlich auf Taste 3, 4, 5 und 8. Außerdem weiß er, dass beim Codeschloss mit der Seriennummer 25F7-ST66 ein 4-stelliger Zugangscode in der richtigen Reihenfolge eingegeben werden muss. Die Frage lautet nun, wie viele Kombinationen muss unser Einbrecher durchgehen, um das Schloss 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, dass 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 beeinflussen. 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.
// Return:      A vector of all permuted strings.
// 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.
// ============================================================================
vector<string> SSTL_Permutation(const char *input)
{
    vector<string> result;
    string cs = input;

    stable_sort(cs.begin(), cs.end());  

    do   
        result.insert(result.end(), cs);
    while(next_permutation(cs.begin(), cs.end())); 

    return result;
}

    Wir haben der Funktion einen Container (vector) vom Typ string spendiert. Dieser Container soll unsere generierten Permutationen aufnehmen und verwalten. Die do while() Schleife erzeugt 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.

    // ============================================================================
// File:        STLPermutation.cpp 
// Description: Implementation of standard STL function next_permutation
// ============================================================================
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// generate associative container pair key
typedef map<char, int> 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.
//              @bOrdered: flag to set optionally ordering On/Off.
// Return:      A vector of all permuted strings.
// 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.
// ============================================================================
vector<string> ISTL_Permutation(const char *input, bool bOrdered/*default=true*/)
{
    POSITION_MAP mapPos;
    vector<string> result;
    string cs = input;

    if(!bOrdered)
        for(unsigned int i=0; i<cs.length(); i++)
            mapPos.insert(pair<char, unsigned int>(cs[i], i));   

    do   
        result.insert(result.end(), cs);   
    while (_next_permutation(cs.begin(), cs.end(), bOrdered ? NULL : &mapPos)); 

    return result;
}

    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, dass 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 lediglich 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.

    Permutation mit Wiederholung

    Bisher haben wir nur Fälle kennengelernt, in welchen die vorliegenden Elemente im string sich nicht wiederholt haben. Zum Beispiel ABC oder 3458 oder monkey. Allerdings kann es auch sein, dass der string mehrere Elemente gleicher Art beinhaltet. ABBA ist ein Beispiel dafür. Folgende Voraussetzungen gelten für Permutationen mit Wiederholungen.

    • Mindestens 2 Elemente der Ausgangsmenge sind identisch, d.h. die Elemente der Ausgangsmenge unterscheiden sich nicht alle voneinander.
    • Es müssen alle (N) Elemente ausgewählt werden.
    • Ein Individualelement kann nicht mehrmals ausgewählt werden, ein Element mit gleicher Eigenschaft hingegen schon. Liegen z.B. 2 rote Kugeln in der Ausgangsmenge, so muss jede der beiden roten Kugeln ausgewählt werden (Wiederholung), eine dritte rote Kugel kann aber nicht ausgewählt werden.

    Berechnet wird die Anzahl an möglichen Permutationen über die Formel:

    Der zusätzlich hinzugekommene Faktor k stellt die Anzahl der Wiederholungen eines Elementes dar. Auch hier gilt .

    So existieren beim string ABBA insgesamt 6 Permuationen. Nämlich diese: AABB, ABAB, ABBA, BAAB, BABA, BBAA. Die bisher beschriebenen iterativen Funktionen reagieren unterschiedlich auf diese neue Situation. Während die Funktion SSTL_Permutation alle Permutationen korrekt berechnet, überspringt die ISTL_Permutation Implementierung 2 Permutationen und gibt nur die strings ABBA, BAAB, BABA, BBAA zurück. Hier sollte man also genau differenzieren.

    Permutation mit Hilfe von Rekursion

    Ein relativ oft gegangener Weg, Permutationen zu errechnen, ist der über die Rekursion. Der Grund hierfür liegt in der Eigenschaft der Fakultät, welche sich hierfür geradezu anbietet. Obwohl die iterative STL-Lösung in der Performance deutlich besser als die rekursive Lösung abschneidet, wollen wir auch diese hier auflisten.

    // ============================================================================
// Function:    REC_Permutation
// Description: Generate all permuted strings for an input string
//              using Recursion
// Parameter:   @input: the input string.
//              @bRepeated: flag to allow optionally element repeat.
// Return:      A vector of all permuted strings.
// ============================================================================
vector<string> REC_Permutation(const char* input, bool bRepeated)
{
    vector<string> result, v1;
    string s1;    
    char ch;
    size_t nLen = strlen(input);      

    if(nLen==1)            // Base case: Add one-char string
        result.insert(result.end(), input);      
    else                    // nLen > 1, need recursion
    {
        for(size_t i=0; i<nLen; i++)
        {
            ch = input[i];       // Extract each char as the first

            // To exclude repeated element
            if (!bRepeated)
            {
                size_t j;

                for (j=0; j<i; j++)
                    if(ch==input[j]) 
                        break;

                if (j<i) continue;   // If i==j, Not a repeated one
            }

            s1 = input;           // Copy the original string
            s1.erase(i, 1);    // Put the rest string into s1

            v1 = REC_Permutation(s1.c_str(), bRepeated); // Recursive 

            for(std::size_type i=0; i < v1.size(); i++)
            {
                s1 = ch + v1[i];   
                result.insert(result.end(), s1);   
            }
        }
    }
    return result;
}

    Die rekursive Lösung verhält sich exakt wie die Funktion SSTL_Permutation wenn das Flag bRepeated false ist. Ist es allerdings auf true gesetzt erzeugt die Funktion REC_Permutation immer alle Permutationen, unabhängig davon ob sich vereinzelte strings wiederholen oder nicht.

    Weitere Algorithmen

    Neben den bisher gezeigten Algorithmen gibt es noch einen weiteren nennenswerten, von Phillip P. Fuchs geschriebenen, Algorithmus welcher in der Geschwindigkeit und Effizienz mit dem aus der STL gleichzieht und sogar unter gewissen Umständen besser abschneidet.

    vector<string> PHIL_Permutation(const char* input)
{
    char a[32];
    strcpy(a, input);
    int N = strlen(a);		// constant index ceiling (a[N] length)
    int ax = N - 1;			// constant index ceiling (a[N] length)
    int *p = new int[N+1];  // target array and index control array
    int i, j, tmp;			// index variables and tmp for swap

    for(i = 0; i < N+1; i++)	// p[N] > 0 controls iteration and the index boundary for i
    p[i] = i;

    vector<string> result;
    result.insert(result.end(), a);      

    i = 1;   // setup first swap points to be ax-1 and ax respectively (i & j)
    while(i < N)
    {
        p[i]--;                // decrease index "weight" for i by one
        j = ax - i % 2 * p[i]; // IF i is odd then j = ax - p[i] otherwise j = ax
        i = ax - i;            // adjust i to permute tail (i < j)

        // set Scope
        {
            tmp = a[j];		// swap(a[i], a[j])
            a[j] = a[i];
            a[i] = tmp;
            result.insert(result.end(), a);      
        }

        i = 1;                 // reset index i to 1 (assumed)
        while (!p[i])          // while (p[i] == 0)
        {
            p[i] = i;           // reset p[i] zero value
            i++;                // set new index value for i (increase by one)
        } 
    } 

    delete [] p;
    return result;
}

    Benchmark

    Um die unterschiedlichen Algorithmen in ihrer Performance und Effizienz testen zu können, habe ich neben den verschiedenen Algorithmen einen Test zum Benchmarken eingebaut. Hier lässt sich deutlich der Unterschied zwischen den unterschiedlichen Algorithmen erkennen. Während die rekursive Methode generell deutlich schlechter als die anderen abschneidet, ist die Methode "STL with SORT" am schnellsten, da die Methode "Implemented STL, Ordered" eben nicht alle Permutationen berechnet. Der Algorithmus von Phillip Fuchs schneidet bei Wiederholungen geringfügig schlechter ab als die STL-Lösung. Dies liegt an der Art der Berechnung. Der Algorithmus von Phillip Fuchs geht nämlich auch bei Wiederholungen alle Permutationen durch. Liegt keine Wiederholung vor, schneidet dieser Algorithmus oft sogar besser als die STL-Lösung ab.

    Der nachfolgende Test wurde auf einem P4 mit 2,56GHz und 1024MB RAM durchgeführt.

    Das war's! Sie finden das Programm samt Quellcode mit den implementierten Algorithmen weiter unten als Visual Studio 2003.NET gepacktes Projekt vor. Die Permutationen werden in einer Textdatei gespeichert und bis zu einer Stringlänge von 5 auch visuell ausgegeben :p .

    Permutationen.zip

    0
  • E

    Gibts noch das E?

    0
  • C

    Dieser Thread wurde von Moderator/in estartu aus dem Forum Die Redaktion in das Forum Archiv verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.

    0
Anmelden zum Antworten