Auflistung aller Groß-Kleinschreibungsmöglichkeiten eines Strings

[seldon]

SeppJ schrieb:

seldon schrieb:

Ich wage mal zu behaupten, dass die bessere Laufzeitkomplexität das bei ausreichender Eingabestringlänge wieder raushaut.

Können wir ja mal Testen, wann der Übergang stattfindet. Würde mich eher wundern, wenn das unter ein paar Millionen Zeichen wären. Habe aber gerade keine Zeit, einen passenden Code zu schreiben .

Ich hab da mal eine einfache next_combination-Funktion geschrieben, die den String von vorne aufrollt (das ist nicht, was TE haben will, aber alle Kombinationen kriegt man so auch, und es dauert weniger lang). Break-Even ist bei mir (gcc 4.8 mit -O3, Ausgabe nach /dev/null umgeleitet) zwischen 19 und 20 Zeichen.

#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

void print_combinations_aux(char *s, size_t pos) {
  if(s[pos] == '\0') {
    puts(s);
  } else if(isalpha(s[pos])) {
    s[pos] = toupper(s[pos]);
    print_combinations_aux(s, pos + 1);
    s[pos] = tolower(s[pos]);
    print_combinations_aux(s, pos + 1);
  } else {
    print_combinations_aux(s, pos + 1);
  }
}

void print_combinations_inplace(char *s) {
  print_combinations_aux(s, 0);
}

void print_combinations(char const *s) {
  char *p = malloc(strlen(s) + 1);
  strcpy(p, s);
  print_combinations_inplace(p);
  free(p);
}

char *next_combination(char *s) {
  // upper -> 0, lower -> 1
  char *p;

  if(*s == '\0') { return NULL; }

  for(p = s; *p; ++p) {
    if(!isalpha(*p)) {
      continue;
    } else if(isupper(*p)) {
      *p = tolower(*p);
      return s;
    } else {
      *p = toupper(*p);
    }
  }

  return NULL;
}

int main() {
  clock_t start, end;
  char buf[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

  start = clock();

  do {
    puts(buf);
  } while(next_combination(buf));

  end = clock();

  fprintf(stderr, "iterativ: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);

  start = clock();

  print_combinations_inplace(buf);

  end = clock();

  fprintf(stderr, "rekursiv: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);

  return 0;
}

Der Vorteil des rekursiven Ansatzes wird geringer, wenn viele Zahlen/Nicht-Buchstaben im String enthalten sind. Das kann man bei Bedarf lösen, indem man vorher einen Index anlegt und in der Rekursion nur noch die Buchstaben verarbeitet.

tw1x: Der zweite Funktionsaufruf wird ausgeführt, nachdem der erste durch ist. Der Mechanismus ist nicht wirklich anders als bei normaler Rekursion; man spricht nur von Baumrekursion, wenn eine rekursive Funktion sich selbst nicht bloß ein-, sondern mehrmals aufruft.

Was die Laufzeitkomplexität angeht, so geht es darum, wie die Länge der Laufzeit mit der Länge des Eingabestrings korreliert. Vereinfacht gesagt: Skaliert ein Algorithmus mit O(n), so dauert die Verarbeitung eines 2000 Zeichen langen Strings grob doppelt so lange wie die eines 1000 Zeichen langen Strings und die eines 4000 Zeichen langen Strings doppelt so lange wie die eines 2000 Zeichen langen. Skaliert ein anderer Algorithmus mit O(2ⁿ), so dauert die Verarbeitung eines 1001 Zeichen langen Strings grob doppelt so lange wie die eines 1000 Zeichen langen Strings und die eines 1002 Zeichen langen Strings doppelt so lang wie die eines 1001 Zeichen langen.

Das bedeutet nicht notwendigerweise, dass der erste Algorithmus für alle Eingaben schneller ist als der zweite, wohl aber, dass er es ab einer bestimmten Eingabelänge ist.

Im vorliegenden Fall gibt es 2ⁿ Kombinationen, die zu ergründen sind. Die rekursive Variante skaliert in O(2ⁿ) (das Erstellen einer einzelnen Kombination geschieht in amortisiert konstanter Zeit), die iterative in O(n2ⁿ). Für kurze Eingaben läuft die iterative Variante schneller, weil Rekursion einen gewissen Overhead mit sich bringt, mit dem sich die iterative Variante nicht herumschlagen muss. Ab einer gewissen Länge (in meiner Messung ~20 Zeichen) führt die schlechtere Komplexitätsklasse aber dazu, dass die rekursive Variante in Führung geht und diese bei immer längeren Eingaben immer weiter ausbaut.

[hsrtrzh<W4]

seldon schrieb:

Im vorliegenden Fall gibt es 2ⁿ Kombinationen, die zu ergründen sind. Die rekursive Variante skaliert in O(2ⁿ) (das Erstellen einer einzelnen Kombination geschieht in amortisiert konstanter Zeit), die iterative in O(n2ⁿ).

Du musst bedenken, dass die Ausgabe immer O(n) Zeit in Anspruch nimmt, also beide Algorithmen in deiner Testmessung immer O(n2ⁿ) Zeit benötigen.

Das wäre der Vorteil der Bit-Lösung, das Inkrementieren geht sehr schnell (selbst mit Bigints). Und das Problem der Sonderzeichen kann mit Bitmasken umgangen werden.

// Bitmask erstellen (Zahl zu 1, Rest zu 0)
bitmask := ... // Bsp: "x99xxx9x" => 0b01100010

Combinations := 2^alphas

for (; combinations--; bitmask++) {
  // String wird lazy generiert aus bitmask und string (1=toupper, 0=tolower)
}

Das ändert auch die Komplexitätsklasse in O(nonalphas + 2^alphas).

[hsrtrzh<W4]

hsrtrzh<W4 schrieb:

das Inkrementieren geht sehr schnell (selbst mit Bigints).

Hmm, nein, das Inkrementieren ist immer noch O(n). Es drückt nur die Konstante noch weiter runter.

[hsrtrzh&lt;W4]

hsrtrzh<W4 schrieb:

hsrtrzh<W4 schrieb:

das Inkrementieren geht sehr schnell (selbst mit Bigints).

Hmm, nein, das Inkrementieren ist immer noch O(n). Es drückt nur die Konstante noch weiter runter.

Sorry, doch nicht, das Inkrementieren ist amortisiert konstant.

[SeppJ]

Da habe ich mich total verschätzt. Die Anzahl der Möglichkeiten ist bei 19 Zeichen selbst ja schon fast in Millionenhöhe (wo ich irgendwo den Übergang zwischen iterativ und rekursiv geschätzt hätte - anscheinend sogar richtig ). Habe nicht bedacht, wie die Zahl der Möglichkeiten wächst.

[SeppJ]

hsrtrzh<W4 schrieb:

hsrtrzh<W4 schrieb:

hsrtrzh<W4 schrieb:

das Inkrementieren geht sehr schnell (selbst mit Bigints).

Hmm, nein, das Inkrementieren ist immer noch O(n). Es drückt nur die Konstante noch weiter runter.

Sorry, doch nicht, das Inkrementieren ist amortisiert konstant.

Was soll an der Bitvariante anders sein als an der iterativen Variante? Du lagerst doch bloß die gleiche Rechnung in eine Hilfsvariable aus. Dadurch änderst du bloß die Konstanten, nicht die Komplexität.

[hsrtrzh&lt;W4]

SeppJ schrieb:

Was soll an der Bitvariante anders sein als an der iterativen Variante? Du lagerst doch bloß die gleiche Rechnung in eine Hilfsvariable aus. Dadurch änderst du bloß die Konstanten, nicht die Komplexität.

Der Unterschied ist nur die Konstante.

Deine next_permutation ist auch amortisiert O(1), das hat seldon falsch gerechnet.

In 2^-2 aller Fälle bricht die Schleife nach 1 Durchgängen ab.
In 2^-3 aller Fälle bricht die Schleife nach 2 Durchgängen ab.
In 2^-4 aller Fälle bricht die Schleife nach 3 Durchgängen ab.
In 2^-5 aller Fälle bricht die Schleife nach 4 Durchgängen ab.
In 2^-6 aller Fälle bricht die Schleife nach 5 Durchgängen ab.
...

$\sum_{i=0}^\infty \frac{i}{2^i} = 2$

Das heisst gleiche Komplexität für SeppJ/mich/seldon bei nur alphas, aber bessere Komplexität bei vielen nonalphas (jedes nonalpha-Bit wird bei mir nur einmal getoggled). Die Bitvariante war ein Versuch, die schlechte Konstante von deinem Ansatz zu verbessern in dem die Chars lazy berechnet werden.

[SeppJ]

hsrtrzh<W4 schrieb:

Die Bitvariante war ein Versuch, die schlechte Konstante von deinem Ansatz zu verbessern in dem die Chars lazy berechnet werden.

Dann lass mal sehen. Am besten gleich fertig in seldons Benchmark eingebaut, damit man damit experimentieren kann.

[hsrtrzh&lt;W4]

#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

void print_combinations_aux(char *s, size_t pos) {
  if(s[pos] == '\0') {
    puts(s);
  } else if(isalpha(s[pos])) {
    s[pos] = toupper(s[pos]);
    print_combinations_aux(s, pos + 1);
    s[pos] = tolower(s[pos]);
    print_combinations_aux(s, pos + 1);
  } else {
    print_combinations_aux(s, pos + 1);
  }
}

void print_combinations_inplace(char *s) {
  print_combinations_aux(s, 0);
}

void print_combinations(char const *s) {
  char *p = malloc(strlen(s) + 1);
  strcpy(p, s);
  print_combinations_inplace(p);
  free(p);
}

char *next_combination(char *s) {
  // upper -> 0, lower -> 1
  char *p;

  if(*s == '\0') { return NULL; }

  for(p = s; *p; ++p) {
    if(!isalpha(*p)) {
      continue;
    } else if(isupper(*p)) {
      *p = tolower(*p);
      return s;
    } else {
      *p = toupper(*p);
    }
  }

  return NULL;
}

void analyze(const char *c, unsigned *bitmask, unsigned *combos, char *togglecase)
{
  unsigned bit=1;
  int i;

  *bitmask = 0;
  *combos = 1;
  for (; *c; c++, bit<<=1)
    if (isalpha(*c))
      *combos <<= 1;
    else
      *bitmask |= bit;

  for (i=0; i<256; i++)
    togglecase[i] = isupper(i) ? tolower(i) : toupper(i);
}

void next_bit_combination(char *c, unsigned *pbitmask, const char *togglecase) {
  unsigned bitmask = *pbitmask;
  *pbitmask = bitmask + 1;
  unsigned diff = bitmask ^ *pbitmask;  
  unsigned least_index;
  do {
    least_index = __builtin_ctz(diff);
    c[least_index] = togglecase[(unsigned char)c[least_index]];
  } while ((diff -= 1u<<least_index));
}

int main() {
  clock_t start, end;
  char buf[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

  start = clock();

    unsigned bitmask, combos;
    char table[256];
    analyze(buf, &bitmask, &combos, table);
    for (; --combos; next_bit_combination(buf, &bitmask, table)) {
      puts(buf);
    }

    // wieder schön grossbuchstabig machen
    next_bit_combination(buf, &bitmask, table);

  end = clock();

  fprintf(stderr, "bittig: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);

  start = clock();

  do {
    puts(buf);
  } while(next_combination(buf));

  end = clock();

  fprintf(stderr, "iterativ: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);

  start = clock();

  print_combinations_inplace(buf);

  end = clock();

  fprintf(stderr, "rekursiv: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);

  return 0;
}

"ABCDEFGHIJKLMNOPQRSTUVWXYZA":
bittig: 7.330000
iterativ: 8.630000
rekursiv: 7.170000

"A B C D E F G H I J K L M N O P Q R S T U V W X Y Z !":
bittig: 4.250000
iterativ: 4.960000
rekursiv: 4.840000

[hsrtrzh&lt;W4]

Da war üble Branch-Prediction im Spiel, die sich auf die Seite von seldon gestelllt hat.

Neue Version:

void next_bit_combination(char *c, unsigned *pbitmask, unsigned startmask, const char *togglecase) {
  unsigned bitmask = *pbitmask;
  *pbitmask = bitmask + 1;
  unsigned diff = (bitmask ^ *pbitmask) & ~startmask;
  *pbitmask = *pbitmask | startmask;
  unsigned least_index;
  if (diff == 1) // damit wird es schneller!
    c[0] = togglecase[(unsigned char)c[0]];
  else
    do {
      least_index = __builtin_ctz(diff);
      c[least_index] = togglecase[(unsigned char)c[least_index]];
    } while ((diff -= 1u<<least_index));
}

"A B C D E F G H I J K L M N O P Q R S T U V W X Y Z !":
bittig: 4.090000
iterativ: 4.960000
rekursiv: 4.890000

"ABCDEFGHIJKLMNOPQRSTUVWXYZA"
bittig: 6.670000
iterativ: 8.640000
rekursiv: 7.310000

http://ideone.com/KvjCzg

[hsrtrzh&lt;W4]

"ABCDEFGHIJKLMNOPQRSTUVWXYZ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"
bittig: 4.090000
iterativ: 5.340000
rekursiv: 14.470000

(einfach int nach long ändern)

[seldon]

Ah, ja. Bei der Laufzeitkomplexität habe ich gedenkfehlert -- mea culpa.

Was den Ansatzvergleich angeht, die Nicht-Buchstaben zu überspringen ist mit allen drei Ansätzen möglich. Halt mal

char **make_letter_index(char *s) {
  char **letters = malloc(strlen(s) * sizeof(char*));

  if(letters) {
    char *p, **q;

    for(p = s, q = letters; *p; ++p) {
      if(isalpha(*p)) {
        *q++ = p;
      }
    }
    *q = NULL;
  }

  return letters;
}

void print_combinations_aux(char *s, char **letters) {
  if(*letters == NULL) {
    puts(s);
  } else {
    **letters = toupper(**letters);
    print_combinations_aux(s, letters + 1);
    **letters = tolower(**letters);
    print_combinations_aux(s, letters + 1);
  }
}

void print_combinations_inplace(char *s) {
  char **letters = make_letter_index(s);

  if(letters) {
    print_combinations_aux(s, letters);
    free(letters);
  }
}

dagegen, das sollte bei vielen Leerzeichen besser abschneiden. Ich kann das mit deiner neuen Funktion im Moment nicht vergleichen, weil diese sich nicht ohne Änderungen in den vorherigen Code einsetzen lässt (zusätzlicher Parameter).

[seldon]

Nachtrag: In Zeile 2

char **letters = malloc((strlen(s) + 1) * sizeof(char*));

[hsrtrzh&lt;W4]

Hat sich gebessert

"ABCDEFGHIJKLMNOPQRSTUVWXYZ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"
bittig: 3.970000
iterativ: 5.000000
rekursiv: 4.290000

Der letzte Code war in ideone um Platz zu sparen. Hier das vollständige Listing:

#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

char **make_letter_index(char *s) { 
  char **letters = malloc(strlen(s) * sizeof(char*)); 

  if(letters) { 
    char *p, **q; 

    for(p = s, q = letters; *p; ++p) { 
      if(isalpha(*p)) { 
        *q++ = p; 
      } 
    } 
    *q = NULL; 
  } 

  return letters; 
} 

void print_combinations_aux(char *s, char **letters) { 
  if(*letters == NULL) { 
    puts(s); 
  } else { 
    **letters = toupper(**letters); 
    print_combinations_aux(s, letters + 1); 
    **letters = tolower(**letters); 
    print_combinations_aux(s, letters + 1); 
  } 
} 

void print_combinations_inplace(char *s) { 
  char **letters = make_letter_index(s); 

  if(letters) { 
    print_combinations_aux(s, letters); 
    free(letters); 
  } 
}

void print_combinations(char const *s) {
  char *p = malloc(strlen(s) + 1);
  strcpy(p, s);
  print_combinations_inplace(p);
  free(p);
}

char *next_combination(char *s) {
  // upper -> 0, lower -> 1
  char *p;

  if(*s == '\0') { return NULL; }

  for(p = s; *p; ++p) {
    if(!isalpha(*p)) {
      continue;
    } else if(isupper(*p)) {
      *p = tolower(*p);
      return s;
    } else {
      *p = toupper(*p);
    }
  }

  return NULL;
}

void analyze(const char *c, unsigned long long *bitmask, unsigned long long *combos, char *togglecase)
{
  unsigned long bit=1;
  int i;

  *bitmask = 0;
  *combos = 1;
  for (; *c; c++, bit<<=1)
    if (isalpha(*c))
      *combos <<= 1;
    else
      *bitmask |= bit;

  for (i=0; i<256; i++)
    togglecase[i] = isupper(i) ? tolower(i) : toupper(i);
}

void next_bit_combination(char *c, unsigned long long *pbitmask, unsigned long long startmask, const char *togglecase) {
  unsigned long long bitmask = *pbitmask;
  *pbitmask = bitmask + 1;
  unsigned long long diff = (bitmask ^ *pbitmask) & ~startmask;
  *pbitmask = *pbitmask | startmask;
  unsigned long long least_index;
  switch (diff) {
  case 3: c[1] = togglecase[(unsigned char)c[1]];
  case 1: c[0] = togglecase[(unsigned char)c[0]]; break;
  case 2: c[1] = togglecase[(unsigned char)c[1]]; break;
  default:
    do {
      least_index = __builtin_ctzll(diff);
      c[least_index] = togglecase[(unsigned char)c[least_index]];
    } while ((diff -= 1ull<<least_index));
  }
}

int main() {
  clock_t start, end;
  //char buf[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZA";
  char buf[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!";

  start = clock();

  unsigned long long bitmask, combos, startmask;
  char table[256];
  analyze(buf, &bitmask, &combos, table);
  startmask = bitmask;
  for (; combos--; next_bit_combination(buf, &bitmask, startmask, table)) {
    puts(buf);
  }

  end = clock();

  fprintf(stderr, "bittig: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);

  puts(buf);
  puts(buf);
  puts(buf);
  puts(buf);

  start = clock();

  do {
    puts(buf);
  } while(next_combination(buf));

  end = clock();

  fprintf(stderr, "iterativ: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);

  start = clock();

  print_combinations_inplace(buf);

  end = clock();

  fprintf(stderr, "rekursiv: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);

  return 0;
}

[seldon]

Deine Variante ist allerdings ziemlich fragil:

$ ./a.out 
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABC
bittig: 0.000000
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!aBC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!AbC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!abC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABc
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!aBc
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!Abc
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!abc
iterativ: 0.000000
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABc
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!AbC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!Abc
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!aBC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!aBc
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!abC
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!abc
rekursiv: 0.000000

[Tw1x]

Ich glaube, ihr wisst nicht ganz, was ich meine...

else if(isalpha(s[pos])) {
    s[pos] = toupper(s[pos]); 
    print_permutations_aux(s, pos + 1);

Bis hier verständlich, Funktion wird einfach aufgerufen...

s[pos] = tolower(s[pos]); 
    print_permutations_aux(s, pos + 1);

Und hier? Hier wird - nachdem die Funktion schon wieder vorm if ist - nochmal aufgerufen!? Wie soll denn das gehen, der Ablauf kommt doch da gar nicht mehr hin!?

Das ist das Ganze, was ich nicht verstehe... wäre cool, wenn mir jemand genau erläutern könnte, wo mein Denkfehler liegt.

[EOP]

Ich weiß zwar nicht wie man die Komplexität theoretisch-informatisch berechnet, aber ich kann auf jeden Fall funktionierende Programme schreiben. :p

EDIT:
"auf jeden Fall" kann man auch durch "wenigstens" oder "zumindest" ersetzen.

[seldon]

Tw1x schrieb:

Ich glaube, ihr wisst nicht ganz, was ich meine...

else if(isalpha(s[pos])) {
    s[pos] = toupper(s[pos]); 
    print_permutations_aux(s, pos + 1);

Bis hier verständlich, Funktion wird einfach aufgerufen...

s[pos] = tolower(s[pos]); 
    print_permutations_aux(s, pos + 1);

Und hier? Hier wird - nachdem die Funktion schon wieder vorm if ist - nochmal aufgerufen!? Wie soll denn das gehen, der Ablauf kommt doch da gar nicht mehr hin!?

Das ist das Ganze, was ich nicht verstehe... wäre cool, wenn mir jemand genau erläutern könnte, wo mein Denkfehler liegt.

Fangen wir vielleicht mal mit einfacher Rekursion an:

// Summe aller natürlichen Zahlen von 0 bis n.
unsigned summe(unsigned n) {
  unsigned s = 0;

  if(n > 0) {
    s = summe(n - 1); // <-- rekursiver Aufruf.

    s += n;           // <--  Wenn der durch ist, geht es hier weiter.
  }

  return s;
}

Wenn n == 0, dann gibt die Funktion 0 zurück, soviel ist klar. Andernfalls holt sie sich über summe(n - 1) die Summe aller Zahlen von 0 bis n - 1, rechnet n drauf und gibt das zurück. Dabei ruft die Funktion sich selbst auf; man nennt einen solchen Aufruf rekursiv. Der neue Funktionsaufruf erhält seine eigenen lokalen Variablen, und wenn er durch ist, geht es mit dem Kontext weiter, aus dem er gestartet wurde. Er kann auch problemlos weitere Aufrufe der selben Funktion auf den Callstack stapeln.

Die einfache Zurückgabe von 0 bei n == 0 (ohne rekursive Funktionsaufrufe) und die Tatsache, dass der Parameter im rekursiven Funktionsaufruf gegen 0 geht, führen dazu, dass diese Funktion auch mal zu einem Ende kommt. Man spricht davon, dass n == 0 die Abbruchbedingung ist.

In der Baumrekursion passiert genau das selbe, nur dass die Funktion sich selbst nicht einmal aufruft, sondern zweimal hintereinander. Der zweite rekursive Aufruf passiert, nachdem der erste durch ist.

[SeppJ]

Tw1x schrieb:

Ich glaube, ihr wisst nicht ganz, was ich meine...

else if(isalpha(s[pos])) {
    s[pos] = toupper(s[pos]); 
    print_permutations_aux(s, pos + 1);

Bis hier verständlich, Funktion wird einfach aufgerufen...

s[pos] = tolower(s[pos]); 
    print_permutations_aux(s, pos + 1);

Und hier? Hier wird - nachdem die Funktion schon wieder vorm if ist - nochmal aufgerufen!? Wie soll denn das gehen, der Ablauf kommt doch da gar nicht mehr hin!?

Das ist das Ganze, was ich nicht verstehe... wäre cool, wenn mir jemand genau erläutern könnte, wo mein Denkfehler liegt.

Nun, Rekursion eben. Sogar ein ziemlich gutes Beispiel dafür, da es nicht so künstlich ist wie andere Beispiele.

Bei jedem Aufruf entstehen zwei Äste, einmal mit dem Zeichen klein geschrieben, einmal groß geschrieben. Diese Äste arbeiten vollkommen unabhängig voneinander! In jedem dieser Äste wird der Spaß dann für das nächste Zeichen wiederholt. Es entstehen vier Äste, jeweils zwei an den zwei alten Ästen. So bekommt man ganz am Ende genau einen Ast für jede Kombination.

Beispiel abc:

"abc"            
               /
            "ab"
            /  \
           /    "abC"
          /
        "a"
        / \     "aBc"
       /   \   /
      /     "aB"
     /         \       
    /           "aBC"
Start
    \           "Abc"
     \         /
      \     "Ab"
       \   /   \
        \ /     "AbC"
        "A"
          \     "ABc"
           \   /
            "AB"
               \
                "ABC"

[hsrtrzh&lt;W4]

Nochmal der letzte Performanceboost (mit Korrektur der <64-Zeichen-Beschränkung):

void bit_combos(char *c)
{
  unsigned long bit=1;
  unsigned i;

  int index[32] = {};
  unsigned alphas = 0;

  unsigned combos = 1;
  const char *p=c;
  for (i=0; *p; p++, bit<<=1, i++)
    if (isalpha(*p)) {
      if (alphas >= 3)
        combos <<= 1;
      assert(alphas < 32);
      index[alphas] = i;
      ++alphas;
    }

  assert(alphas >= 3);

  char togglecase[256];
  for (i=0; i<256; i++)
    togglecase[i] = isupper(i) ? tolower(i) : toupper(i);

  for (i=0; i<combos; i++) {
    unsigned diff = (i ^ (i+1));

#define toggle(idx) \
    c[index[idx]] = togglecase[(unsigned char)c[index[idx]]]

    puts(c); toggle(0);                       // 000
    puts(c); toggle(0); toggle(1);            // 001
    puts(c); toggle(0);                       // 010
    puts(c); toggle(0); toggle(1); toggle(2); // 011
    puts(c); toggle(0);                       // 100
    puts(c); toggle(0); toggle(1);            // 101
    puts(c); toggle(0);                       // 110
    puts(c); toggle(0); toggle(1); toggle(2); // 111

    if (diff == 1)
      toggle(3);
    else {
      unsigned least_index;
      do {
        least_index = __builtin_ctz(diff);
        toggle(least_index+3);
      } while ((diff -= 1u<<least_index));
    }
  }
}

int main() {
  //char buf[] = "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!ABCD"; // geht jetzt
  char buf[] = "  A1  B2  C3  D4  E5  F6  G7  H8  I9  J10  K11  L12  M13  N14  O15  P16  Q17  R18  S19  T20  U21  V22  W23  X24  ";

  start = clock();

  bit_combos(buf);

  end = clock();

  fprintf(stderr, "bittig: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);

  ...
}

"  A1  [...]  X24  "
bittig  : 4.860000
iterativ: 5.690000
rekursiv: 5.140000

Ich denke, schneller gehts nicht mehr.