Auflistung aller Groß-Kleinschreibungsmöglichkeiten eines Strings

[seldon]

SeppJ schrieb:

Rekursion ist auch etwas ineffizient.

(...)

void next_combination(char *str);

Liefert die nächste Kombination, indem es einfach von einer Seite aus durch die Zeichenkette geht und den ersten Buchstaben umwandelt.

Uh-huh. Und wenn du next_combination in O(1) hinkriegst, dann reden wir darüber, ob die rekursive Variante ineffizient ist.

[SeppJ]

seldon schrieb:

Uh-huh. Und wenn du next_combination in O(1) hinkriegst, dann reden wir darüber, ob die rekursive Variante ineffizient ist.

Nein, nicht weniger (laufzeit-) komplex. Aber mit schöner kompakter Schleife, statt dauernden Funktionsaufrufen.

[seldon]

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

[EOP]

Rekursion mag nicht der effizienteste Weg sein, aber ich finde das Konzept schön.

EDIT:
Wobei ich auch noch eine Rekursion in der Rekursion einbaue.

[SeppJ]

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 .

[Tw1x]

gut, also euer laufzeitkomplexitätsproblem versteh ich jetz nicht, mir isses egal, wie lange mein 10-zeichen-string braucht, hauptsache unter 12 std und dann eben noch richtig...

was das mit der baumrekursion bringt, verstehe ich noch nicht, wie kann die funktion in zeile 35 (kommentierter code) ausgeführt werden, wenn er davor schon die funktion aufruft, das kann doch nicht funktionieren oder?

[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;
}