4. Auflistung aller Groß-Kleinschreibungsmöglichkeiten eines Strings

Auflistung aller Groß-Kleinschreibungsmöglichkeiten eines Strings

  • T

    Hallo,

    danke für eure Antworten, die letzte Antwort verstehe ich gar nicht, das heißt, ich verstehe noch "void" und andere Schlüsselwörter, aber da ich ein ziemlicher Anfänger bin, verstehe ich von dem Code gar nichts...

    Ich habe mir mein Programm nochmal angeschaut und jetzt die Reihenfolge umdrehen wollen, mit der das aufgelistet wird (nicht mehr vorne groß-klein-groß-klein-... sondern hinten an den Strings); habe das auch jetzt geschafft, durch die Einführung einer weiteren Zählvariable k, die ich statt dem log2-Zeugs da verwende.
    Dann ist mir noch aufgefallen, dass ich die 128 in der inneren for-Schleife falsch gewählt habe, da muss ne 64 hin. Somit hab ich die Lösung fast, jetzt nur noch schnell die Zahlen ignorieren lassen und nochmal testen, dann funktionierts.
    Ich werde die lauffähige Lösung hier noch reineditieren, danach kann geclosed werden.

    0
  • E

    Tw1x schrieb:

    die letzte Antwort verstehe ich gar nicht, das heißt, ich verstehe noch "void" und andere Schlüsselwörter, aber da ich ein ziemlicher Anfänger bin, verstehe ich von dem Code gar nichts...

    Ja, eigentlich wundere ich mich selber was ich da zusammengebastelt habe. Aber es fumktioniert. Auch mit Zahlen, Sonderzeichen.

    0
  • ?

    Jetzt, da du deine Aufgabe selber gelöst hast, kann ich ja meinen Ansatz zeigen.

    int main(void) {
  int i, j, k;
  char test[] = "v76tcthg4j";
  const int test_size = strlen(test);
  for(i = 0; i < (1<<(test_size - 3)); i++) {
    printf("%3d. Möglichkeit: ", i+1);
    for (j=k=0; j<test_size; j++, k++) {
      while (isdigit(test[j]))
        putchar(test[j++]);
      putchar((i & (1<<k)) ? toupper(test[j]) : test[j]);
    }
    putchar('\n');
  }
}

    @EOP: Das ist der Beweis, dass man mit ein bisschen C-Kenntnis viel weiter kommt als mit ein bisschen C++-Kenntnis. Dein Code ist langsam (O(2^(alphas+nonalphas)) statt O((2^alphas)+nonalphas), Rekursion, Zwischenspeichern in vector) und umständlich (win-zeugs, m_len redundand, Rekursion, warum replace, Pseudo-OOP).

    0
  • E

    Was ist denn an m_len redundant? Ich brauch ja ne Abbruchbedingung für die Rekursion. So berechne ich sie einmal und "gut is".

    0
  • ?

    Du hast doch schon m_input.length() ?

    0
  • T

    Ok, das "reineditieren" von meinem letzten Post einfach wegdenken, habe es nicht geschafft, die Zahlen mit rein zu kriegen...

    Mein Dank geht an hsrtrzh<W4, dankesehr, dein Code funktioniert perfekt... nahezu perfekt zumindest, werde die Reihenfolge noch umdrehen, will nämlich, dass am Stringende zuletzt das Zeichen variiert wird, also so:

    ...
V76TCTHg4j
V76TCTHg4J
V76TCTHG4j
V76TCTHG4J

    Wie ich sehe, arbeitest du mit Bitverschiebung? (Bitverschiebungen mag ich gar nicht, die verstehe ich zwar grad so, aber ich finde die so unübersichtlich...)
    Könntest du den Code noch ausführlich kommentieren, dass ich ihn verstehe? Funktionieren tut er ja...

    Danke für die Lösung des Problems!

    0
  • E

    @ hsrtrzh<W4

    Versuch mal dein Programm mit

    char test[] = "g4j";

    oder

    char test[] = "g4jx";

    und dann test mal meins.

    Fällt dir was auf?

    0
  • T

    Ich verstehe nicht ganz, bist du sicher dass du den

    char test[]

    und nicht den

    char temp[]

    meintest?

    Ich stelle nur fest, dass es mit dem x ca. 10 mal jede Möglichkeit auflistet, also z.B.
    128.
    128.
    128.
    ...

    aber ich verstehe nicht ganz, was du meinst... oder meinst du die Unabhängigkeit des Input-Strings bei deinem Code? Das weiß ich schon, das ist nur für genau den String der Code von mir^^

    0
  • T

    So, hab die Lösung von hsrtrzh<W4 umgeschrieben, dass er mir den Output in ne *.txt schreibt, und bin vorerst befriedigt mit dem Ergebnis.

    Danke für die schnelle Hilfe; hach, ich liebe Foren! xD

    Beste Grüße & gn8
    Tw1x

    0
  • E

    original:

    char test[] = "v76tcthg4j";

    und mit

    char test[] = "g4j";

    Ausgabe:
    1. Möglichkeit "g4j"
    und das war's dann schon auch.

    0
  • ?

    Ihr macht's euch aber kompliziert.

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

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

void print_permutations_inplace(char *s) {
  print_permutations_aux(s, 0);
}

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;
}
    0
  • E

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

    E#1:
    Ah, wohl für free.

    E#2:
    Nö wohl doch nicht.

    0
  • T

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

    0
  • ?

    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.

    0
  • T

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

    0
  • ?
     

    #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;
}
    0
  • E

    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.

    0
  • T

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

    0
  • Mod

    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.

    0
  • E

    SeppJ schrieb:

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

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

    0
Anmelden zum Antworten