Auflistung aller Groß-Kleinschreibungsmöglichkeiten eines Strings

Tw1x

wie jetzt? es gibt also vorgefertigte funktionen für eine permutation? verstehe ich das jetz richtig? wie gerne ich den code testen würde... bin leider nimmer am pc und kann mir erst in 45 min nen c-compiler fürs handy holen... mal sehen, danke schonmal jetzt^^

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.

@tw1x: Das sind keine vorgefertigten Funktionen. Der komplette Code ist in dem Schnipsel enthalten.

Tw1x

Achso...
könntest du vielleicht noch bitte die "codeschnipsel" kommentieren, dass ich weiß, wo was zu machen ist/passiert? verstehe nämlich fast nix davon...

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

/*
 * Das Herzstück der ganzen Angelegenheit.
 * 
 * print_permutations_aux gibt alle Kombinationen an Klein- und Großbuchstaben
 * hinter der übergebenen Position (Parameter pos) aus; alles vor pos wird
 * unverändert gelassen.
 * Dieses Verhalten wird erreicht, indem print_permutations, wenn sie einen
 * Buchstaben findet, diesen durch sein großgeschriebenes Gegenstück ersetzt,
 * alle Kombinationen an Klein- bzw. Großbuchstaben dahinter erzeugt -- dies
 * durch rekursiven Aufruf ihrer selbst -- dann den Buchstaben durch sein
 * kleingeschriebenes Gegenstück ersetzt und das ganze erneut macht.
 * 
 * Das nennt sich auch "Baumrekursion."
 */ 
void print_permutations_aux(char *s, size_t pos) {
  if(s[pos] == '\0') {
    /* Ende des Strings erreicht: Eine Kombination wurde fertiggestellt
     * und kann ausgegeben werden.
     */
    puts(s);
  } else if(isalpha(s[pos])) {
    /* Buchstabe gefunden.*/

    /* Zunächst die Kombinationen mit Großbuchstaben an dieser Stelle */
    s[pos] = toupper(s[pos]);
    print_permutations_aux(s, pos + 1);

    /* Dann die mit Kleinbuchstaben. */
    s[pos] = tolower(s[pos]);
    print_permutations_aux(s, pos + 1);
  } else {
    /* Andere Zeichen als Buchstaben werden übersprungen. */
    print_permutations_aux(s, pos + 1);
  }
}

/*
 * Frontendfunktion. Diese ist für den direkten Gebrauch gedacht, damit kein
 * Positionsparameter angegeben werden muss. Der übergebene Buffer wird
 * verändert.
 */
void print_permutations_inplace(char *s) {
  print_permutations_aux(s, 0);
}

/*
 * Frontendfunktion für konstante Strings; der übergebene Buffer wird nicht
 * verändert, sondern eine Kopie angelegt und dieser für die Berechnung benutzt.
 */
void print_permutations(char const *s) {
  char *p = malloc(strlen(s) + 1);
  strcpy(p, s);
  print_permutations_inplace(p);
  free(p);
}

int main() {
  print_permutations("g4jx");

  return 0;
}

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

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.

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?

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.

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 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<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.