Alle möglichen kombinationen eines strings?
-
Ä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!!!
-
jo du hast recht! (hab ich auch nicht bezweifelt ) thx!