Alle möglichen kombinationen eines strings?



  • hi,
    wie durchlaufe ich am einfachsten alle möglichen kombinationen eines strings?
    bsp:

    string = "12";
    /*
    kombinationen:
    11
    12
    21
    22
    */
    
    string = "ab";
    /*
    kombinationen:
    aa
    ab
    bb
    ba
    */
    
    string = "axb";
    /*
    kombinationen:
    axb
    axx
    abx
    abb
    bax
    baa
    bxx
    xab
    xba
    xbb
    xaa
    aaa
    xxx
    bbb
    bba
    bbx
    xxa
    xxb
    xax
    xbx
    aax
    aab
    aba
    axa
    axx
    bxx
    */
    
    string = "%&";
    /*
    kombinationen:
    %%
    &&
    %&
    &%
    */
    


  • Rekursiv!!!

    1: Rekursionstiefe = Stringlaenge
    2: in jeder Rekursion For- schleife 1 .. Stringlaenge (0 .. Stringlaenge -1)

    Ergebnis aller Rekursionen Ausgeben oder in Stringliste schreiben

    voila



  • und was mach ich dann in der for-schleife?
    sorry ich krieg das einfach nicht hin.. das problem ist ja auch noch, dass nicht nur abx sondern auch ad.skrj3btr9437b4ß940562cv0 vorkommen kann, also quasi nicht in der länge begrenzt ist...



  • Aus diesem Grund ist hat "DerAltenburger" auch geschrieben das du rekursiv arbeiten sollst. Dann ist es egal wie lang der String ist. 😉



  • ja toll ich kann aber aus der zeile:
    2: in jeder Rekursion For- schleife 1 .. Stringlaenge (0 .. Stringlaenge -1)
    nicht besonders viel schließen



  • Ähm... er meint alle Möglichkeiten, nicht nur jedes Zeichen einmal in beliebiger Position, d.h. Jedes zeichen kann auch mehrmals vorkommen, etc. Sieht man doch an seinem Beispiel:

    123=
    111
    112
    113
    121
    122
    123
    131
    132
    133
    211
    212
    213
    221
    222
    223
    231
    232
    233
    311
    312
    313
    321
    322
    323
    331
    332
    333
    

    - d.h. man braucht so viele Schleifen, wie der String lang ist, bei einem 5-Zeichen-String braucht man 5 Schleifen, etc. und dann sone Art Counter laufen lassen.

    - Windoof



  • Hab mich grad mal herangesetzt und habe eine Funktion dafür geschrieben, die - man lese und staune - funktioniert:

    void __fastcall TForm1::Button1Click(TObject *Sender)
    {
        TStringList* slTemp=new TStringList;
        TStringList* Spalten=new TStringList;
        String sTemp=Edit1->Text;
    
        // Alle Zeichen durchgehen
        for(int Position=1;Position<=Edit1->Text.Length();++Position)
        {
            // Bei jedem Zeichen jede Potenz durchlaufen
            for(int Potenz=Edit1->Text.Length()-1;Potenz>=0;--Potenz)
            {
                int Anzahl=1;
                for(int Temp=0;Temp<Potenz;++Temp)
                    Anzahl*=Edit1->Text.Length();
                String Spalte;
    
                // Für jede Potenz Zeichen hinzufügen
                for(int i=0;i<Anzahl;++i)
                    Spalte=Spalte+String(Edit1->Text[Position]);
                Spalten->Add(Spalte);
            }
        }
    
        // Einzelspalten zusammenfassen (E-Spalte + d-Spalte + i-Spalte + t-Spalte + 1-Spalte [Edit1])
        for(int i=0;i<Edit1->Text.Length();++i)
            for(int j=1;j<Edit1->Text.Length();++j)
                Spalten->Strings[i]=Spalten->Strings[i]+Spalten->Strings[j*Edit1->Text.Length()+i];
    
        // Übrige Spalten löschen
        for(int i=Spalten->Count-1;i>=Edit1->Text.Length();--i)
            Spalten->Delete(i);
    
        // Spaltenlängen anpassen
        for(int i=1;i<Edit1->Text.Length();++i)
            while(Spalten->Strings[i].Length()<Spalten->Strings[0].Length())
                Spalten->Strings[i]=Spalten->Strings[i]+Spalten->Strings[i];
    
        // Spaltenweise die Zeilen speichern
        for(int i=1;i<=Spalten->Strings[0].Length();++i)
        {
            String sTemp="";
            for(int j=0;j<Spalten->Count;++j)
                sTemp=sTemp+String(Spalten->Strings[j][i]);
            slTemp->Add(sTemp);
        }
        slTemp->SaveToFile("c:\\tmp.txt");
        delete slTemp;
        delete Spalten;
        sTemp.~String();
    }
    

    Edit1: Edit-Feld (wie überraschend).
    Probier's mal aus.



  • Ähm, DerAltenburger, ist das das, was Du meinst? Kaum, oder?

    Er sagt Rekursiv. Und so kannst Du Dir mehr als den halben Code ersparen, wenn Du es wirklich Rekursiv machst.
    Das heisst, eine Funktion, die dann immer sich selbst aufruft. Dabei musst Du aber beachten, dass die Rekursion korrekt wieder gelöst wird, sonst wirds ein Stackoverflow geben...

    - Adrian



  • hallo, nur nebenbei: ist unter dem stichwort
    "permutation"
    gut zu finden.



  • elise,

    elise schrieb:

    hallo, nur nebenbei: ist unter dem stichwort
    "permutation"
    gut zu finden.

    bei Permutationen sind keine Wiederholungen erlaubt. Ich schätze, wir reden hier von Variationen mit Wiederholung.

    Und zum Thema Rekursion allgemein: Rekursive Lösungen lassen sich häufig eleganter programmieren. Wenn jedoch eine halbwegs überschaubare iterative Lösung existiert, ist diese oft performanter bzw. verbraucht weniger Ressourcen.
    Also wenn es schnell gehen muß, würde ich persönlich immer die iterative Variante vorziehen.



  • dschensky schrieb:

    bei Permutationen sind keine Wiederholungen erlaubt. Ich schätze, wir reden hier von Variationen mit Wiederholung.

    Und zum Thema Rekursion allgemein: Rekursive Lösungen lassen sich häufig eleganter programmieren. Wenn jedoch eine halbwegs überschaubare iterative Lösung existiert, ist diese oft performanter bzw. verbraucht weniger Ressourcen.
    Also wenn es schnell gehen muß, würde ich persönlich immer die iterative Variante vorziehen.

    nach dem eingangsbeispiel würde ich sagen: nein, ohne wiederholung.
    aber muss der mensch ja selber wissen.
    mir ist nach langer einfindung die rekusive machmal einfacher.. kommt aber klar immer auf das problem an, und was sich "denktechnisch" anbietet.



  • @windoof
    funktioniert super! danke 👍



  • und wie muss ich die funktion abwandeln, wenn ich die werte alle "nacheinander" ein eine listbox einfügen will?
    d.h.:
    immer wenn eine neue kombination errechnet ist -> sofort in listbox, und nicht erst warten bis alle kombinationen errechnet sind und dann in die listbox



  • //---------------------------------------------------------------------------
    void __fastcall TForm1::Button1Click(TObject *Sender)
    { AnsiString Variante="";
      Memo1->Clear();
      Rekursion(Edit1->Text,Edit1->Text.Length(),Variante);
    }
    //---------------------------------------------------------------------------
    //Rekursive procedure !!!
    //Parameter VARIANTE muss Call by Referenz übergeben werden !!!
    void __fastcall TForm1::Rekursion(AnsiString Satz, int Rek, AnsiString &Variante)
    { if (Rek>0)
      { Rek--;
        for (int i=1;i<=Satz.Length();i++)
        { if (Rek>0)
            Rekursion(Satz,Rek,Variante+Satz[i]);
          else
            Memo1->Lines->Add(Variante+Satz[i]);
     }}}
    //---------------------------------------------------------------------------
    

    Braucht ca 47 sec für "123456" !!!
    auf 1700er Pentium



  • Sehr schön. So ganz durchgestiegen bin ich noch nicht, aber trotdem: sehr schön!

    DerAltenburger schrieb:

    Braucht ca 47 sec für "123456" !!!

    Und ohne Ausgabe vermutlich keine Sekunde?
    btw: Das call by reference ist hier nicht nötig.



  • DerAltenburger schrieb:

    <Edit: Zitate auf das Notwendigste beschränken. Danke!>

    funktioniert wirklich super!
    jetzt hab ich noch ein problem:
    was mache ich wenn ich alle kombinationen barauche die zwischen 3 und 6 zeichen lang sind?



  • Dann gibst Du noch nen Parameter (int Min) mit.

    Die Ausgabe (in Memo) erfolgt erst bei Rek>= Min

    Anstelle der Laenge des Stringes ubergibst Du die gewünschte maximalzahl (sollte NICHT groesser sein als Laenge!!!)



  • nein falsch verstanden 😃 ich meine ich habe den String "abcdefghijklmnopqurstuwxyz"
    und min:3; max:4;

    ausgabe:
    aaa
    aab
    aac
    ...
    aba
    ...
    zza
    zzb
    ...
    zzz
    aaaa
    aaab
    aaac
    ...
    aaba
    ...
    zzza
    zzzb
    ...
    zzzz



  • Kannst du C++? Kannst die Funktion doch selbst so umbauen, dass erh alt nur 3 Zeichen ausgibt...



  • Konsti schrieb:

    nein falsch verstanden 😃 ...

    Joooo, Du meine Antwort!

    Wenn Du als Parameter Rek Deine maximalzahl anstelle der Stringlaenge uebergibst, rkursiert das ganze nur so oft!!! (Count- Down- Zaehler)

    Die Ausgabe machst Du nicht nur am Ende der Rekursion (else- Zweig), sondern schon wenn Variante Deine mindestlaenge hat!

    Voila 😉

    @Windoof
    Hast Du auch konstruktive Tips? Er will nicht NUR 3 Zeichen lange Ausgaben!!! 😉


Anmelden zum Antworten