Auflistung aller Groß-Kleinschreibungsmöglichkeiten eines Strings
-
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
-
"ABCDEFGHIJKLMNOPQRSTUVWXYZ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" bittig: 4.090000 iterativ: 5.340000 rekursiv: 14.470000(einfach int nach long ändern)
-
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).
-
Nachtrag: In Zeile 2
char **letters = malloc((strlen(s) + 1) * sizeof(char*));
-
Hat sich gebessert
"ABCDEFGHIJKLMNOPQRSTUVWXYZ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" bittig: 3.970000 iterativ: 5.000000 rekursiv: 4.290000Der 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; }
-
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
-
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.
-
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.
-
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.
-
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"
-
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.140000Ich denke, schneller gehts nicht mehr.
-
Achso!
Ah, jetzt!Ok, also gleichzeitig, während die Funktion schon wieder ausgeführt wird, arbeitet die am Kleinbuchstabe weiter (oder Groß~, das untere halt...).
Jetzt hab ichs verstanden.
Das heisst meine Idee ist vollkommen im A****, da das Bitgefummel ja überhaupt nicht nötig ist. xDDann werde ich mal den Code noch an meine Ausgabe anpassen, eine Liste mit 128 Möglichkeiten habe ich allerdings schon ausgedruckt heute, also fürs nächste Mal was gelernt, für dieses Mal zu früh aufgegeben und meinen Schrott-Code verwendet.^^
Danke für alle Hilfen und Erklärungen, werde mich wieder an euch wenden beim nächsten Problem^^
-
Tw1x schrieb:
Ok, also gleichzeitig, während die Funktion schon wieder ausgeführt wird, arbeitet die am Kleinbuchstabe weiter (oder Groß~, das untere halt...).
Nein, hier nicht wirklich gleichzeitig. Die Äste werden (so wie ich sie gemalt habe) von oben nach unten abgearbeitet. Schließlich wird jeder Funktionsaufruf für sich vollständig ausgeführt, bevor der nächste dran kommt.
Zuerst kommt also der Aufruf vom ersten Ast ("a"), dieser ruft seinen ersten Ast auf ("ab"), dieser ruft wieder seinen ersten Ast auf ("abc"). In "abc" ist die Abbruchbedingung erfüllt. Die Zeichenkette wird ausgegeben und die Funktion kehrt zurück zu "ab". Dort wird nun der zweite Ast ("abC") aufgerufen. Dieser gibt "abC" aus und kehrt zurück zu "ab". "ab" ist nun fertig und kehrt zurück zu "a". "a" führt nun seinen zweiten Ast aus ("aB"). Und so weiter.
Man kann dies aber wunderbar gut parallelisieren. Da die Äste unabhängig voneinander sind, kann man jeden Ast von einem eigenen Thread/Prozess bearbeiten lassen. Dies ist eine mächtige und gängige Möglichkeit der Parallelisierung. (Auf ein paar Details müsste man noch achten, aber das ist hier nicht wichtig)
Das heisst meine Idee ist vollkommen im A****, da das Bitgefummel ja überhaupt nicht nötig ist. xD
Nun, die Bitgefummelmethode scheint am Ende doch die schnellst zu sein, wenn du den kleinen Performancewettbewerb hier im Thread verfolgt hast. Nicht viel, aber immerhin deutlich messbar. Bitgefummel ist nämlich sehr, sehr schnell. Es ist bloß nicht angenehm zu programmieren. Meine Methode ist sicherlich etwas einfacher zu verstehen und die Rekursionsmethode hat eben ihre eigene Eleganz (auch wenn ich persönlich kein Fan von Rekursion bin*).
*: Ich bin wohl geschädigt, weil ich zu oft ihren Missbrauch um ihrer selbst willen gesehen habe
.
-
hsrtrzh<W4 schrieb:
Ich denke, schneller gehts nicht mehr.
Naja, du hast da immer noch eine Beschränkung auf 32 Buchstaben drin.
Ohnehin ist der Vorsprung nicht besonders groß und teilweise Dingen zuzuschreiben, die auch in die anderen Ansätze passen (etwa der togglecase-Trick oder das Inlining der letzten drei Buchstaben). Auch ist nicht klar, inwieweit die Geschwindigkeit plattformabhängig ist -- zum Beispiel gibt es auf ARMs die ctz-Instruction, die du für die Hälfte aller Kombinationen benutzt, nicht.
Jedenfalls komme ich mit
char **make_letter_index(char *s) { char **letters = malloc((strlen(s) + 1) * sizeof(char*)); if(letters) { char *p, **q; for(p = s, q = letters; *p; ++p) { if(isalpha(*p)) { *q++ = p; } } memmove(q - 2, q - 3, sizeof(char*) * 3); q[-3] = NULL; } return letters; } void print_combinations_aux(char *s, char **letters) { if(*letters == NULL) { ++letters; puts(s); *letters[2] ^= 32; puts(s); *letters[2] ^= 32; *letters[1] ^= 32; puts(s); *letters[2] ^= 32; puts(s); *letters[2] ^= 32; *letters[1] ^= 32; *letters[0] ^= 32; puts(s); *letters[2] ^= 32; puts(s); *letters[2] ^= 32; *letters[1] ^= 32; puts(s); *letters[2] ^= 32; puts(s); *letters[2] ^= 32; *letters[1] ^= 32; *letters[0] ^= 32; } 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; letters = make_letter_index(s); if(letters) { print_combinations_aux(s, letters); free(letters); } }schon schneller zum Ergebnis als dein Code. Da ist dann aber auch eine Beschränkung auf mehr als drei Buchstaben drin, so dass andere Fälle ggf. vorher abgefangen werden müssten.
-
Ihr solltet bei den Messungen noch bedenken, dass das puts einen gewaltigen Teil der Zeit ausmachen dürfte. Das heißt kleine Unterschiede in der Gesamtlaufzeit können riesige Unterschiede bei der Eigenlaufzeit des Algorithmus bedeuten. Um das auszugleichen könnte man beispielsweise (nach Kontrolle, ob auch alles richtig ist) statt der Ausgabe bloß den ersten Buchstaben zu einer globalen Variable addieren. Dies sollte Wegoptimierungen des Compilers verhindern und benötigt fast keine Eigenzeit.
Es ist natürlich auch ein guter Einwand, dass die eigentliche Laufzeit des Algorithmus nicht so entscheidend ist, wenn das puts so lange braucht. Das heißt, man hat gute Gründe, sich auf funktionierende, übersichtliche und einfache Lösungen zu beschränken (d.h. Minuspunkte für Bitgefummel, trotz Siegs bei der Geschwindigkeit).
-
SeppJ schrieb:
Meine Methode ist sicherlich etwas einfacher zu verstehen und die Rekursionsmethode hat eben ihre eigene Eleganz (auch wenn ich persönlich kein Fan von Rekursion bin*).
Mit 13 effektiver Zeilen code (flip kann man als 14. hinzufugen) spiele ich wohl ganz oben mit.
-
Mal ganz abgesehen davon, dass wir hier nicht im C++-Forum sind und dein Code C++ + WinAPI war: Dein Code funktioniert nicht. Wirft eine Exception aus std::basic_string::at, weil pos benutzt wird, bevor geprüft wird, ob es noch innerhalb des Strings ist.
-
ich bring auch mal ein pferd ins rennen
sollte knapp auf dem 2. platz landen 
void bit_combos2(char *str){ size_t len = strlen(str); size_t *pos = malloc(sizeof(size_t)*len); if(pos){ size_t ll = 0; len = 0; char *s = str; for(;*s;s++){ *s = tolower(*s); if(islower(*s)){ ll <<= 1; ll |= 1; pos[len++] = s - str; } } size_t l; ll >>= 3; puts(str); for(;ll--;){ for(l = 0;(str[pos[l]] & 32) == 0;l++){ str[pos[l]] = str[pos[l]] ^ 32; }; str[pos[l]] ^= 32; #define toggle(x) str[pos[len - 1 - x]] ^= 32 puts(str); toggle(0); // 000 puts(str); toggle(0); toggle(1); // 001 puts(str); toggle(0); // 010 puts(str); toggle(0); toggle(1); toggle(2); // 011 puts(str); toggle(0); // 100 puts(str); toggle(0); toggle(1); // 101 puts(str); toggle(0); // 110 puts(str); toggle(0); toggle(1); toggle(2); // 111 #undef toggle } free(pos); } }@edit: so kommt das mäuschen fast sogar auf die 1
-
EOP schrieb:
SeppJ schrieb:
Meine Methode ist sicherlich etwas einfacher zu verstehen und die Rekursionsmethode hat eben ihre eigene Eleganz (auch wenn ich persönlich kein Fan von Rekursion bin*).
Mit 13 effektiver Zeilen code (flip kann man als 14. hinzufugen) spiele ich wohl ganz oben mit.
void bit_combos3(char *str){ size_t len = 0,ll = -1,l=strlen(str),*pos; if(l && (pos = malloc(sizeof(size_t) * l))){ char *s = str; for(;*s;s++){ if(isupper((*s = toupper(*s)))){ pos[len++] = s - str; } } for(ll = ~(ll<<len) + 1;ll--;){ puts(str); for(l = len;l-- && ((str[pos[l]] ^= 32) & 32) == 0;); } free(pos); } }verdammt, schon wieder verloren
