Rekurstion / Permutation auf STring

Kellerautomat

Mir ist immer noch nicht klar, was die Funktion genau tut. 'source' ist also dein Set and Zeichen? Was ist 'deep'? Die Laenge des Strings? Was gibt die Funktion zurueck?

Sorry, hab den Code reinkopiert, der ist mittlerweile total vermurkst.

Also ich wollte source übergeben quase "abc", solange deep < string_länge, die funktion rekursiv aufrufen und die Buchstaben erst mal nur ausgeben.
Später evtl. speichern oder so.

Aber ich kriegs heut gar nicht auf die Reihe.

Dachte mit bisschen durch Source durchiterieren und bisschen cout << *it würde das gleich klappten.

Wie macht man das richtig?

Also der Code soll am Ende das machen, was hald seine "Iterierende" Variante macht , um mir x - For Schleifen zu ersparen.

std::string test = "ab";

for (auto i = test.begin(); i != test.end(); i++){

   for (auto j = test.begin(); j != test.end(); j++){

   std::cout << *i << *j << "\n";
}
}

Kellerautomat

mach aus jedem schleifen-body eine funktion, denk nach welche parameter du brauchst und wie sich die aendern.

sinn? for ist mal viel schneller als rekursion.

Jester

Bevor Du losprogrammierst solltest Du Dir klar machen wie genau die Rekursion funktionieren soll. Wenn ich es richtig verstehe, dann willst Du alle Zeichenketten einer gewissen Länge ausgeben, die sich mit den Zeichen eines gegebenen Strings bilden lassen.

Schritt 1: Du brauchst ein Abbruchkriterium. Nämlich der einfachste Fall, wenn die Länge 0 ist, dann ist die Funktion sehr einfach.

Schritt 2: Überleg Dir, wie Du die Funktion für Länge x realisieren würdest unter der Annahme, dass Du schon eine Funktion hast, die es für Länge x-1 tut.
Nämlich: Liste alle Strings der Länge x-1 und kombiniere sie mit allen möglichen Zeichen.

Bevor Dir das nicht komplett klar ist, lohnt es sich imo nicht dazu Code zu schreiben.

Jester

Kellerautomat schrieb:

sinn? for ist mal viel schneller als rekursion.

Und wenn die Länge der Strings nicht zwei sondern drei ist? Fünf? Siebzehn?

camper

Kann z.B. so aussehen:

void comb(std::string source, size_t depth, std::string prefix=""){
    if ( depth == 0 )
        std::cout << prefix << '\n';
    else
        for (auto c : source)
            comb(source, depth-1, prefix+c);      
}

Die verbleibende for-Schleife kann man nat. auch noch eliminieren.
Oder zur Übung auch einfach mal nicht-rekursiv schreiben.

@Jester

Mein Ansatz war jetzt eher :

Ich gebe der Funktin einen String mit 3 Zeichen, der Position bzw. das Zeichen das ich gerade "anzeige" und die gesamte Länge :

v

oid reku_sucks(std::string source, int deep, int pos){

	for (auto it = source.begin(); it != source.end() ; it++){

		if (pos < deep){
			reku_sucks(source, deep, pos + 1);
		}

	}

Aber ich glaube der Code ist immer noch falsch, und ich habe keinen Plan wo ich die Ausgabe mit std::cout << *it setzten soll.

Ich habs jetzt erst mal mit "in String speichern" gelöst, weil ich mit dem std::cout << nicht weiterkomme.

int reku_sucks(std::string source, std::string out,  int deep, int pos){

	static int ctr = 0;

	for (auto it = source.begin(); it != source.end(); it++){

		out[pos] = *it;

		if (pos+1 < deep){

			reku_sucks(source, out, deep, pos + 1);
		}
		else{
			std::cout << out << "\n";
			ctr++;
		}
	}

	return ctr;

Diese Variante geht jetzt... aber naja... könnte ich statt out[pos] irgendwie mit push_back arbeiten`?

SeppJ

beg_ schrieb:

Diese Variante geht jetzt... aber naja... könnte ich statt out[pos] irgendwie mit push_back arbeiten`?

Ja, natürlich. Das wäre sogar wesentlich besser, da du dann nicht einen String passender Länge übergeben müsstest. Sich auf korrekte Nutzereingaben zu verlassen, wenn es nicht nötig wäre, ist nie eine gute Idee. Daher: Mit leeren String starten (guck mal, wie camper das gemacht hat) und dann in jeder Stufe mit push_back anhängen.

Die Ausgabe machst du dann, wenn du deine gewünschte Tiefe erreicht hast.

Hm, muss mir das noch genauer ansehen, aber in mein obriges Bspl. kann ich jetzt push_back nicht wriklich einbauen.

Daher: Mit leeren String starten (guck mal, wie camper das gemacht hat) und dann in jeder Stufe mit push_back anhängen.

Die Ausgabe machst du dann, wenn du deine gewünschte Tiefe erreicht hast.

Ich kann das nicht auf meine Version übertragen. Bin zu doof dafür. reku_sucks suckt wirklich.

JA!!! Ich habs mit push_back endlich zusammenbekommen!

int comb(std::string source, std::string out, int pos){

 static int ctr = 0;  	

	 for (auto it = source.begin(); it != source.end(); it++){

 		out.push_back(*it);

 		if(pos+1  == source.length()){
 			std::cout << out << "\n";
 			ctr++;

 		}else{  			
 			comb(source, out, pos+1); 			
 		}

 		out.pop_back();
 	}

   return ctr;

}//END COMB

Mein Fazit : Wer Rekursiv programmiert ist komisch veranlagt und echt eklig!!!!

Th69

Lern einfach mal eine funktionale Sprache (z.B. Haskell) und du wirst ganz schnell Rekursion verstehen (auch komplexere).

Danke für den Tipp, aber das hat leider leider keinen Platz mehr auf meiner ToDo Liste :p :p