Auflistung aller Groß-Kleinschreibungsmöglichkeiten eines Strings

[EOP]

seldon schrieb:

EOP schrieb:

Dumme Frage:
Wofür ist print_permutations_inplace nötig? (Bin nicht mehr ganz nüchtern).

Ist streng genommen nicht nötig, aber wenn du schon einen schreibbaren Buffer hast, der geclobbert werden kann, macht es wenig Sinn, eine Kopie davon anzulegen. In dem Fall kann _inplace benutzt werden.

Den könntest du ja auch direkt an print_permutations_aux weiterreichen. Ich sehe nicht wirklich einen Vorteil in dieser Konstruktion.
Werd's mir aber morgen nochmal durch den Kopf gehen lassen.

[Tw1x]

ok, also zeilen 36 - 66 habe ich verstanden, die baumrekursion selbst nicht, ich glaube entweder ich bin müde, oder ich verstehs grad nicht...
werde mir das an dem beispiel "g4jx" morgen genaustens aufzeichnen, dann versteh ichs vielleicht.

danke für eure bemühungen, vor allem die von hsrtrzh<W4 und seldon, vielen herzlichen dank!

so, erstmal gn8 @all^^

[SeppJ]

Bitgefummel ist hier gar nicht nötig. Rekursion ist auch etwas ineffizient. Besonders da wir hier ein Problem haben, welches ziemlich natürlich eine Zahl auf eine Buchstabenkombination abbildet (so wie es der Bitfummelalgorithmus macht) und somit sehr schön als einfache Schleife programmierbar wäre. Das war auch die Idee der Originallösung des TE, bloß das Bitfummeln sparen wir uns:

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. Ist die Umwandlung von klein nach groß, ist man fertig. Ist sie von groß nach klein, dann hat man einen Überlauf und geht zum nächsten Buchstaben und treibt das Spiel noch weiter.

Also einfach nur binäres Hochzählen. Dafür brauchen wir nämlich gar keine Zählvariable (ohnehin unpraktisch, wenn die Zeichenkette lang wird), sondern nehmen einfach die Zeichenkette selbst als Datenspeicher.

Kurz: Eine ganz einfache Schleife mit einer klaren Abbruchbedingung. Nur wenige Zeilen Programmieraufwand.

[EOP]

SeppJ schrieb:

Bitgefummel ist hier gar nicht nötig. Rekursion ist auch etwas ineffizient.

Ich finde meine Lösung immer noch kewl. :p

[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&lt;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&lt;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