aus schleifen eine rekursion erzeugen

hi

Es geht um Kombinatorik.
Also:
aus den Buchstaben f[]="ab";
soll-> aa,ab,ba,bb werden.

char f[]="ab";
char t[]="  ";
void k(char f[])
{
	for(int a=0; a<3; ++a)
	{
		t[0]=f[a];
		for(int i=0; i<3; ++i)
		{
			t[1]=f[i];
		}
	}
}

Daraus möchte ich eine Rekursion machen. -> Nur bekomme ich das überhaubt nicht hin..

cu

Ponto

Ich mach mal lieber mit std::string als mit boesen char *

void k(std::string const & f, std::string const & result,  int len)
{
  if (len == 0) {
    std::cout << result << std::endl;
    return;
  }
  std::string temp = result + " ";
  for (std::string::size_type i = 0; i != f.size(); ++i)
  {
    temp[temp.size()-1] = f[i];
    k(f, temp, len-1);
  }
}

hi

Krass. Wie hast dud as so schnell hinbekommen?

cu

Ponto

Rekursion ist nicht schwer, man muss nur wissen was man will. Zum Beispiel war deine Aufgabenstellung nicht eindeutig. Wieviele Zeichen sollen jeweils in der Ausgabe erscheinen? Da das nicht klar war, hab ich einfach dies als das Element genommen, über das die Rekursion geht.

Dann muss man sich klar machen, wie die Rekursion funktionieren soll: Wenn ich alle Zeichenketten aus dem Alphabet f, der Länge n haben will, gehe ich einfach über alle Zeichen aus f und hänge die Zeichenketten der Länge n-1 dran.

Beim Programmieren kommt dann zuerst die Abbruchbedingung, und dann die überlegte Rekursion.

Wenn man sich dann auch keine Gedanken um Effizienz macht und Datenstrukturen verwendet, die kaum Fehler erlauben (std::string), geht es sehr schnell. Effizienter ist es zum Beispiel insgesamt nur zwei strings zu haben, anstatt jedesmal ein temp anzulegen. Aber Optimierungen macht man nur, wenn man sie wirklich braucht.

hu

Du erzählst das so locker

std::string temp = result + " ";

-> Wozu das?

cu

Ponto

rulzi schrieb:

hu

Du erzählst das so locker
std::string temp = result + " ";
-> Wozu das?

cu

Damit hab ich mir selbst widersprochen. Denn das war eine kleine Optimierung, um nicht in der Schleife jedesmal einen neuen std::string zu erzeugen. Am einfachsten wäre die Schleife mit:

for (std::string::size_type i = 0; i != f.size(); ++i)
{
  k(f, result + f[i], len-1);
}

hi

result + f[i]

-> Es müsste doch result immer länger und länger werden..aber warum ist das nicht so?

cu

Ponto

rulzi schrieb:

result + f[i]
-> Es müsste doch result immer länger und länger werden..aber warum ist das nicht so?

Hier wird result nicht verlängert. Es wird ein neuer temporärer String angelegt, der die Summe darstellt. Wenn du schreibst,

int a = 2, b =3;
a + b;

wird weder a noch b verändert. Dagegen wird ein temporäres int mit der Summe erzeugt und gar nicht verwendet.

Der string würde bei folgenden Operationen länger werden:

result = result + f[i];
result.append(f[i]);
result += f[i];

hi

Hm, ich arbeite sehr selten mit strings.
Ich versuche gerade deine string variante mit feldern darzustellen, aber irgendwie wird das auch nix...

char f[]="abc";
char t[4]="";
int laenge=0;
void rek(char *f)
{
    if(laenge>3)    
    {
        cout<<t<<endl;
        return;   
    }    
    for(int i = 0; i != strlen(f); ++i)
    {
        ++laenge;
        t[laenge]=f[i];
        rek(f);    
    }   
}

cu

Ponto

Mal ohne strings:

#include <string>
#include <iostream>

char const * f = "ab";
char result[5];

void k(char const * f, char * r,  int len)
{
  if (len == 0) {
    std::cout << result << std::endl;
    return;
  }

  for (int i = 0; i != strlen(f); ++i)
  {
    *r = f[i];
    k(f, r + 1, len-1);
  }
}

int main()
{
   result[4] = 0;
   k(f, result, 4);
}

hu

Wenn die Funktion aber nur einen Parameter hat?
(wie bei mir es der Fall ist)- denn so würde ich es erstmal machen wollen - zum besseren verständnis.

cu

Ponto

rulzi schrieb:

Wenn die Funktion aber nur einen Parameter hat?
(wie bei mir es der Fall ist)- denn so würde ich es erstmal machen wollen - zum besseren verständnis.

Du kannst um die Version mit Parametern, einen Wrapper mit nur einem Parameter schreiben.

Dein Programm scheitert unter anderem daran, dass die Laenge kein Parameter sondern eine globale Variable ist. Man kann auch damit arbeiten, indem der Wert nach dem rekursiven Aufruf wieder zurückgesetzt wird, aber ein Parameter ist einfacher.

hi

Könntest du mir das bitte mit nur einem Parameter ummodeln?
Bitte

cu

Ponto

rulzi schrieb:

Könntest du mir das bitte mit nur einem Parameter ummodeln?

Dazu muss man zuerst genau wissen, was du haben möchtest. Also, was ist die Eingabe und was ist die Ausgabe?

hu

char f[]="abcdefghji";
int LAENGE=strlen(f);
k(char t[])
{
...
}

cu

Ponto

Was ist das t[]?

hi

Also: der Funktion k wird das Zeichenfeld übergeben wo die ganzen Zeichen drin stehen mit denen alle möglichen kombinationen durchgeführt werden sollen. (hatte das in meinem vorhergehenden thread falsch dargestellt).

cu

Ponto

rulzi schrieb:

Also: der Funktion k wird das Zeichenfeld übergeben wo die ganzen Zeichen drin stehen mit denen alle möglichen kombinationen durchgeführt werden sollen. (hatte das in meinem vorhergehenden thread falsch dargestellt).

Welche Länge haben die Kombinationen? Man kann normalerweise die Länge beliebig wählen. Bei "ab" und der Länge 3 hat man:

aaa
aab
aba
abb
baa
bab
bba
bbb

hi

Die Länge sollte als globale variable existieren.

cu