Auflistung aller Groß-Kleinschreibungsmöglichkeiten eines Strings

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

[seldon]

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

[Tw1x]

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.

[EOP]

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.

[seldon]

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.

[SeppJ]

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"

[hsrtrzh&lt;W4]

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

Ich denke, schneller gehts nicht mehr.

[Tw1x]

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

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