Permutation

Mister Wing

Hallo,

im Artikel

http://www.c-plusplus.net/forum/viewtopic-var-t-is-178286.html

wird beschrieben wie ich die Permutation in einer gegebenen Menge mit allen Kombinationen implementieren kann.

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

Mein Problem ist, wie kann ich in einer gegeben Menge alle Permutationen von Dreierkombinationen ermitteln? Also als Beispiel:

Ich habe 20 Punkte und möchte alle 3 Kombinationen dieser 20 Punkte ermitteln.

(P_1,P_2,P_3) (P_1,P_2,P_4) (P_1,P_2,P_5) ...

Wobei (P_1,P_2,P_3) und (P_3,P_2,P_1) das selbe ist. Also geordnet und ohne Wiederholung.
Welche Bedingung muss ich mit einbauen?

Fellhuhn

Hm, geht es auch ohne STL?
Finde ich einfacher.

Such mal nach Passwort-Cracker, solltest sogar hier im Forum fündig werden. Diese Art von Permutation wird dort benötigt und Codes die so einen implementieren findet man zur genüge

Nanyuki

Tippgeber schrieb:

Such mal nach Passwort-Cracker, solltest sogar hier im Forum fündig werden. Diese Art von Permutation wird dort benötigt und Codes die so einen implementieren findet man zur genüge

Willst du damit sagen, dass die Passwörter "abcd" und "dcba" gleichwertig sind?

Fellhuhn

vector<string> nonSSTL_Permutation(const char *input)
{
    vector<string> result;
    string cs(input);
    stable_sort(cs.begin(), cs.end());  

    int length = cs.length();
    for(int i = 0; i < length - 2, i++)
      for(int ii = i + 1; ii < length - 1; ii++)
        for(int iii = ii + 1; iii < length; iii++)
          result.push_back(string(cs[i]) + cs[ii] + cs[iii]);

    return result;
}

Geht mit Templates wohl noch einfacher aber so geht es auch.

Mister Wing

Es muss aber geordnet sein. Demzufolge dürfen auch keine Wiederholungen enthalten sein.
Bei deinem Beispiel ist "abcd" und "dcba" das selbe, sprich eine Wiederholung.
Wenn ich also aus 4 Buchstaben alle Permutationen ohne Wiederholung erstelle, sollte es nur eine Möglichkeit geben, nämliche eine. -> "abcd"
Nun zurück zu meine Problemestellung. Ich möchte beispielsweise aus "abcd" alle Dreierkombinationen bilden.

"abc" "abd" "bcd" "acd"

Wie kann ich das nun sinnvoll umsetzen?

vector<string> nonSSTL_Permutation(const char *input)
{
    vector<string> result;
    string cs(input);
    stable_sort(cs.begin(), cs.end());  

    int length = cs.length();
    for(int i = 0; i < length - 2, i++)
      for(int ii = i + 1; ii < length - 1; ii++)
        for(int iii = ii + 1; iii < length; iii++)
          result.push_back(string(cs[i]) + cs[ii] + cs[iii]);

    return result;
}

Wie kann ich in der dritten Schleife die Bedingung setzen?

Nanyuki schrieb:

Tippgeber schrieb:

Such mal nach Passwort-Cracker, solltest sogar hier im Forum fündig werden. Diese Art von Permutation wird dort benötigt und Codes die so einen implementieren findet man zur genüge

Willst du damit sagen, dass die Passwörter "abcd" und "dcba" gleichwertig sind?

Nein, das habe ich überlesen. Macht die Sache sogar einfacher.

Fellhuhn

Mister Wing schrieb:

Wie kann ich in der dritten Schleife die Bedingung setzen?

Welche Bedingung? Funzt doch. Zumindest wenn man meine Flüchtigkeitsfehler rausnimmt.

Nichts doppelt und auch sortiert.

vector<string> nonSSTL_Permutation(const char *input)
{
    vector<string> result;
    string cs(input);
    stable_sort(cs.begin(), cs.end());  

    int length = cs.length();
    for(int i = 0; i < length - 2; i++)
      for(int ii = i + 1; ii < length - 1; ii++)
        for(int iii = ii + 1; iii < length; iii++)
          result.push_back(string() + cs[i] + cs[ii] + cs[iii]);

    return result;
}

Funktioniert jetzt hald nur für 3 aus 4... So wie ich das sehe.
Matlab?

Fellhuhn

Gerold P schrieb:

Funktioniert jetzt hald nur für 3 aus 4... So wie ich das sehe.
Matlab?

Funktioniert auch für 3 aus 1.000.

Gerold P.

Wie schon gesagt, habs nicht ausprobiert, hab auch meinen C Compiler jetzt gelöscht.

Dachte nur wegen dem " Length - 2 " aber hab jetzt keien Lust drüber nachzudenken.

War nicht bös gemeint.