communityWir suchen ständig neue Tutorials und Artikel! Habt ihr selbst schonmal einen Artikel verfasst und seid bereit dieses Wissen mit der Community zu teilen? Oder würdet ihr gerne einmal über ein Thema schreiben das euch besonders auf dem Herzen liegt? Dann habt ihr nun die Gelegenheit eure Arbeit zu veröffentlichen und den Ruhm dafür zu ernten. Schreibt uns einfach eine Nachricht mit dem Betreff „Community Articles“ und helft mit das Angebot an guten Artikeln zu vergrößern. Als Autor werdet ihr für den internen Bereich freigeschaltet und könnt dort eurer literarischen Ader freien Lauf lassen.

Permutationen - Weitere Algorithmen PDF Drucken E-Mail
Benutzerbewertung: / 13
SchwachPerfekt 
Geschrieben von: Kristian   
Freitag, den 23. September 2005 um 19:26 Uhr
Beitragsseiten
Permutationen
Weitere Algorithmen
Alle Seiten

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 das 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:

formula

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

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:    FREC_Permutation
// Description: Generate all permuted strings for an input string
//              using Recursion
// Parameter:   @input: the input string.
//              @result: the buffer, where permutations are stored
//              @bRepeated: flag to allow optionally element repeat.
// ============================================================================
void FREC_Permutation(const std::string& input, std::vector<std::string>& result, 
                      bool bRepeated)
{
    std::vector<std::string> v1;
    std::string s1;    
    char ch;
    size_t nLen = input.length();      
 
    if(nLen == 1)               // Base case: Add one-char string
        result.push_back(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.clear();             // Clear, because we cal this recursively
            FREC_Permutation(s1, v1, bRepeated); // Recursive 
 
            for(size_t i = 0; i < v1.size(); i++) {
                s1 = ch + v1[i];   
                result.push_back(input);  
            }
        }
    }
}

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

void PHIL_Permutation(const std::string& input, std::vector<std::string>& result)
{
    std::string a(input);   
    int N = a.length();    // 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 index boundary for i
        p[i] = i;
 
    result.push_back(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.push_back(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;
}

Benchmark

Um die unterschiedlichen Algorithmen in ihrer Performance und Effizienz testen zu können, habe ich einen kurzen Test zum Benchmarken eingebaut. Hier lässt sich deutlich der Unterschied zwischen den unterschiedlichen Algorithmen erkennen. Während die rekursiven Methoden generell deutlich schlechter als ihre iterativen Konkurrenten abschneiden, sind die Methoden "Implemented STL" am schnellsten. Allerdings berechnen nicht alle Algorithmen dieselbe Anzahl an Permutationen.

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

permute

Die Methode "STL with SORT" erzeugt trotz Sortierung exakt die Hälfte der Permutationen, die beispielsweise Phillip Fuchs liefert. In unserem Beispiel haben wir absichtlich eine Wiederholung eingebaut um den eingangs genannten Unterschied zwischen den Algorithmen zu demonstrieren. Nehmen wir einmal an, wir übergeben die Zeichenkette aba an die Methode "Recursive, Repeated". Das Resultat sähe folgendermaßen aus: aab, aba, aba, aab, baa, baa.

Offensichtlich stimmt die Zahl der Permutationen, mit dem bei drei Elementen zu erwartenden Ergebnis überein, sofern man die klassische n! Formel ansetzt. Doch für uns erscheint das Ergebnis doppelt. Die letzten beiden Zeichenketten sind identisch. Das Zeichen a wird vom Algorithmus einfach per Index unterschieden, d.h. für den Algorithmus ist a nicht gleich a. Auch der Algorithmus von Phillip Fuchs berechnet, wie die rekursive Methode, stur alle Elemente im Array ohne auf den Inhalt Rücksicht zu nehmen.

Weiterhin bleibt festzuhalten das der Phillip Fuchs im direkten Vergleich geringfügig schlechter als die STL Lösung abschneidet. Insgesamt zeigt sich allerdings das beide Algorithmen äußerst effizient arbeiten, jedoch unterschiedlich bei mehrfach auftretenden Elementen reagieren.

Das kurze Konsolenprogramm mit nur 10 Elementen ist letztlich auch nur von bedingter Aussagekraft. Der Großteil der Zeit wird für das Einfügen der Resultate in den vector benötigt und das verlangsamt nicht nur die Berechnungszeit, es limitiert auch die maximale Anzahl von Elementen. Da dieser Schritt allerdings in allen Algorithmen durchgeführt wird, wird das Verhältnis zwischen den Algorithmen nicht verfälscht. Die bloße Berechnung der Permutationen vollzieht sich dementsprechend deutlich rasanter. Sie können den vector bei Bedarf entfernen und nackte Benchmarks durchführen. Das Programm verzichtet bei mehr als 10 Elementen ohnehin auf den vector und nutzt standardmäßig eine Variante des STL Algorithmuses, der die Resultate umgehend in eine Datei schreibt. Beachten Sie allerdings, dass bereits bei 12 unterschiedlichen Elementen die Datei eine Größe von über 5 GB annimmt.

Schluss

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



Zuletzt aktualisiert am Montag, den 23. April 2012 um 00:23 Uhr
 
AUSWAHLMENÜ